Submission #1610694


Source Code Expand

#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif

#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;

typedef pair<int, int> pii;

typedef long long LL;

template<typename T> inline bool chkmax(T &x, const T &y) {
	return x < y ? x = y, 1 : 0;
}

#ifdef DEBUG
char *input_file, *output_file;
#endif

struct IO {
	static const int maxn = (1 << 25) + 10;

	char a[maxn], *s, b[maxn], *t;

	void INPUT() {
		s = a;
		t = b;
		#ifdef DEBUG
		FILE *f = fopen(input_file, "r");
		a[fread(a, 1, sizeof a, f)] = 0;
		#else
		a[fread(a, 1, sizeof a, stdin)] = 0;
		#endif
	}

	void OUTPUT() {
#ifdef DEBUG
		FILE *f = fopen(output_file, "w");
		fwrite(b, 1, t - b, f);
#else
		fwrite(b, 1, t - b, stdout);
#endif
	}

	operator int() {
		int x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator LL() {
		LL x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator char() {
		while(*s <= 32) {
			++s;
		}
		char ret = *s;
		++s;
		return ret;
	}

	inline void out(int x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(int x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(LL x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(LL x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(char c) {
		*t++ = c;
		return;
	}

	inline void out(char *s) {
		while(*s >= ' ') {
			*t++ = *s++;
		}
		return;
	}
}io;

void Main();

int main(int argc, char *argv[]) {
#ifdef DEBUG
	input_file = argv[1];
	output_file = argv[2];
#endif
	io.INPUT();
	Main();
	io.OUTPUT();
	return 0;
}

//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------

const int maxn = 1e5 + 100;

int n, m;
map<int, int> e[maxn];
int par[maxn];
queue<pii> q;

int F(int u) {
	return par[u] == u ? u : par[u] = F(par[u]);
}

void Main() {
	n = io;
	forn(i, 1, n) {
		par[i] = i;
	}
	rep(i, n - 1 << 1) {
		int u = io, v = io;
		++e[u][v];
		++e[v][u];
		q.push(mp(u, v));
	}
	while(!q.empty()) {
		int u, v;
		tie(u, v) = q.front();
		u = F(u);
		v = F(v);
		q.pop();
		if(e[u][v] > 2) {
			io.out("NO\n");
			return;
		}
		if(e[u][v] < 2) {
			continue;
		}
		if(SZ(e[v]) > SZ(e[u])) {
			swap(u, v);
		}
		par[F(v)] = F(u);
		for (auto it: e[v]) {
			int w = it.X, x = it.Y;
			if(w == u) {
				continue;
			}
			e[u][w] += x;
			e[w][u] += x;
			q.push(mp(u, w));
			e[w].erase(v);
		}
		e[v].clear();
		++m;
	}
	if(m == n - 1) {
		io.out("YES\n");
	}
	else {
		io.out("NO\n");
	}
	return;
}

Submission Info

Submission Time
Task E - Blue and Red Tree
User OMTWOCZWEIXVI
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4903 Byte
Status WA
Exec Time 343 ms
Memory 30848 KB

Compile Error

./Main.cpp: In function ‘void Main()’:
./Main.cpp:279:17: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
    io.out("NO\n");
                 ^
./Main.cpp:303:17: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
   io.out("YES\n");
                 ^
./Main.cpp:306:16: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
   io.out("NO\n");
                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 3
AC × 39
WA × 14
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 4 ms 8064 KB
in10.txt AC 137 ms 30848 KB
in11.txt WA 165 ms 27392 KB
in12.txt WA 156 ms 27392 KB
in13.txt WA 159 ms 27392 KB
in14.txt WA 161 ms 27392 KB
in15.txt WA 159 ms 27392 KB
in16.txt WA 148 ms 27392 KB
in17.txt WA 155 ms 27392 KB
in18.txt WA 155 ms 27392 KB
in19.txt WA 173 ms 27392 KB
in2.txt AC 4 ms 8064 KB
in20.txt WA 150 ms 27392 KB
in21.txt AC 188 ms 27648 KB
in22.txt AC 148 ms 27648 KB
in23.txt AC 160 ms 27648 KB
in24.txt AC 157 ms 27648 KB
in25.txt AC 157 ms 27776 KB
in26.txt AC 182 ms 27392 KB
in27.txt WA 162 ms 27392 KB
in28.txt WA 160 ms 27392 KB
in29.txt WA 168 ms 27392 KB
in3.txt AC 4 ms 8064 KB
in30.txt WA 169 ms 27392 KB
in31.txt AC 343 ms 30848 KB
in32.txt AC 307 ms 30848 KB
in33.txt AC 316 ms 30848 KB
in34.txt AC 321 ms 30848 KB
in35.txt AC 318 ms 30848 KB
in36.txt AC 306 ms 30848 KB
in37.txt AC 301 ms 30848 KB
in38.txt AC 324 ms 30848 KB
in39.txt AC 309 ms 30848 KB
in4.txt AC 145 ms 30848 KB
in40.txt AC 304 ms 30848 KB
in41.txt AC 313 ms 30848 KB
in42.txt AC 305 ms 30848 KB
in43.txt AC 307 ms 30848 KB
in44.txt AC 304 ms 30848 KB
in45.txt AC 319 ms 30848 KB
in46.txt AC 319 ms 30848 KB
in47.txt AC 306 ms 30848 KB
in5.txt AC 128 ms 30848 KB
in6.txt AC 314 ms 30848 KB
in7.txt AC 137 ms 30848 KB
in8.txt AC 129 ms 30848 KB
in9.txt AC 134 ms 30848 KB
sample1.txt AC 4 ms 8064 KB
sample2.txt AC 4 ms 8064 KB
sample3.txt AC 4 ms 8064 KB