Submission #524118


Source Code Expand

Copy
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


struct State {
	int i, parent, j; bool b;
	State() { }
	State(int i_, int parent_, int j_, bool b_): i(i_), parent(parent_), j(j_), b(b_) { }
};
void compute_lowlinks(const vector<vector<int> > &g, vector<int> &ord, vector<int> &low) {
	int n = g.size();
	ord.assign(n, -1); low.assign(n, -1);
	int order = 0;
	vector<State> stk;
	for(int ii = 0; ii < n; ii ++) if(ord[ii] == -1) {
		stk.push_back(State(ii, -1, 0, false));
		while(!stk.empty()) {
			State s = stk.back(); stk.pop_back();
			if(s.j == 0)
				low[s.i] = ord[s.i] = order ++;
			if(s.b)
				low[s.i] = min(low[s.i], low[g[s.i][s.j-1]]);
			if(g[s.i].size() == s.j)
				continue;
			int v = g[s.i][s.j];
			if(ord[v] == -1) {
				stk.push_back(State(s.i, s.parent, s.j+1, true));
				stk.push_back(State(v, s.i, 0, false));
			}else if(v != s.parent) {
				stk.push_back(State(s.i, s.parent, s.j+1, false));
				low[s.i] = min(low[s.i], ord[v]);
			}else {
				stk.push_back(State(s.i, s.parent, s.j+1, false));
			}
		}
	}
}

inline bool is_bridge_edge(int i, int j, const vector<int> &ord, const vector<int> &low) {
	return ord[i] < low[j] || ord[j] < low[i];
}

struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if(x != y) {
			if(data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

vector<int> t_parent;
vi t_ord;

void tree_getorder(const vector<vi> &g, int root) {
	int n = g.size();
	t_parent.assign(n, -1);
	t_ord.clear();

	vector<int> stk; stk.push_back(root);
	while(!stk.empty()) {
		int i = stk.back(); stk.pop_back();
		t_ord.push_back(i);
		for(int j = (int)g[i].size() - 1; j >= 0; j --) {
			int c = g[i][j];
			if(t_parent[c] == -1 && c != root)
				stk.push_back(c);
			else
				t_parent[i] = c;
		}
	}
}

int main() {
	int N;
	while(~scanf("%d", &N)) {
		int A = N * 2 + 1;
		vector<vi> g(A * 2);
		vpii edges(A);
		rep(i, A) {
			int X, Y;
			scanf("%d%d", &X, &Y), -- X, -- Y;
			g[X].push_back(A + Y);
			g[A + Y].push_back(X);
			edges[i] = mp(X, A + Y);
		}
		vector<vi> tree(A * 2 + 1);
		UnionFind uf; uf.init(A * 2);
		rep(i, A) {
			int x, y; tie(x, y) = edges[i];
			if(uf.unionSet(x, y)) {
				tree[x].push_back(y);
				tree[y].push_back(x);
			}
		}
		rep(i, A * 2) if(uf.root(i) == i) {
			tree[A * 2].push_back(i);
			tree[i].push_back(A * 2);
		}
		tree_getorder(tree, A * 2);
		vector<int> edgenum(A * 2, 0);
		rep(i, A) {
			int x, y; tie(x, y) = edges[i];
			++ edgenum[x == t_parent[y] ? x : y];
		}
		vi edgesum(A * 2 + 1, 0);
		for(int ix = (int)t_ord.size() - 1; ix > 0; -- ix) {
			int i = t_ord[ix], p = t_parent[i];
			edgesum[i] += edgenum[i];
			edgesum[p] += edgesum[i];
		}
		int odds = 0;
		rep(i, A * 2) if(i == uf.root(i))
			odds += edgesum[i] % 2 == 1;
		vi ord, low;
		compute_lowlinks(g, ord, low);
		rep(i, A) {
			int x, y; tie(x, y) = edges[i];
			bool ans;
			if(!is_bridge_edge(x, y, ord, low)) {
				ans = odds == 0;
			} else {
				int t = odds;
				t -= edgesum[uf.root(x)] % 2 == 1;
				int a = x == t_parent[y] ? y : x;
				t += edgesum[a] % 2 == 1;
				t += (edgesum[uf.root(x)] - edgesum[a] - 1) % 2 == 1;
				ans = t == 0;
			}
			puts(ans ? "OK" : "NG");
		}
	}
	return 0;
}

Submission Info

Submission Time
Task D - みんな仲良し高橋君
User anta
Language C++11 (GCC 4.9.2)
Score 0
Code Size 4764 Byte
Status WA
Exec Time 679 ms
Memory 55032 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:123:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &X, &Y), -- X, -- Y;
                                     ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 4
WA × 11
AC × 25
WA × 23
Set Name Test Cases
Sample example_0.txt, example_1.txt, example_2.txt
Subtask1 bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_bubun_0.txt, random_bubun_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_bubun_0.txt, square_bubun_1.txt
All bone_0.txt, bone_1.txt, bone_2.txt, bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, example_0.txt, example_1.txt, example_2.txt, handmade_0.txt, handmade_1.txt, handmade_2.txt, handmade_3.txt, komakai_0.txt, komakai_1.txt, komakai_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_0.txt, random_1.txt, random_bubun_0.txt, random_bubun_1.txt, renket_0.txt, renket_1.txt, smallrand_0.txt, smallrand_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_0.txt, square_1.txt, square_bubun_0.txt, square_bubun_1.txt, supersmall_0.txt, supersmall_1.txt, threeren_0.txt, threeren_1.txt, treebase_0.txt, treebase_1.txt, treebase_2.txt, example_0.txt, example_1.txt, example_2.txt
Case Name Status Exec Time Memory
bone_0.txt WA 498 ms 51988 KB
bone_1.txt WA 490 ms 51992 KB
bone_2.txt WA 490 ms 51984 KB
bone_bubun_0.txt WA 116 ms 15600 KB
bone_bubun_1.txt AC 35 ms 2340 KB
bone_bubun_2.txt WA 166 ms 20484 KB
example_0.txt AC 27 ms 808 KB
example_1.txt AC 26 ms 800 KB
example_2.txt AC 27 ms 800 KB
handmade_0.txt AC 26 ms 800 KB
handmade_1.txt AC 27 ms 800 KB
handmade_2.txt AC 26 ms 800 KB
handmade_3.txt AC 26 ms 800 KB
komakai_0.txt AC 572 ms 54648 KB
komakai_1.txt AC 588 ms 53364 KB
komakai_2.txt AC 569 ms 55032 KB
komakai_bubun_0.txt AC 511 ms 53252 KB
komakai_bubun_1.txt AC 502 ms 53372 KB
komakai_bubun_2.txt AC 508 ms 53384 KB
maxrand_0.txt AC 636 ms 53372 KB
maxrand_1.txt AC 679 ms 53424 KB
maxrand_bubun_0.txt WA 591 ms 52820 KB
maxrand_bubun_1.txt WA 536 ms 52820 KB
random_0.txt AC 39 ms 2468 KB
random_1.txt AC 334 ms 31444 KB
random_bubun_0.txt WA 40 ms 2716 KB
random_bubun_1.txt WA 148 ms 15628 KB
renket_0.txt WA 548 ms 52580 KB
renket_1.txt WA 552 ms 52572 KB
smallrand_0.txt AC 27 ms 916 KB
smallrand_1.txt AC 27 ms 804 KB
smallrand_bubun_0.txt WA 28 ms 784 KB
smallrand_bubun_1.txt WA 28 ms 928 KB
smallrand_bubun_2.txt WA 26 ms 920 KB
square_0.txt WA 382 ms 46144 KB
square_1.txt WA 380 ms 46520 KB
square_bubun_0.txt WA 375 ms 46876 KB
square_bubun_1.txt WA 284 ms 35000 KB
supersmall_0.txt AC 27 ms 804 KB
supersmall_1.txt AC 26 ms 800 KB
threeren_0.txt WA 520 ms 51428 KB
threeren_1.txt WA 536 ms 51804 KB
treebase_0.txt WA 422 ms 42368 KB
treebase_1.txt WA 98 ms 10432 KB
treebase_2.txt WA 314 ms 31836 KB