Submission #2998494
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
struct UnionFind
{
vector<int> par, rank;
UnionFind(int N) {
par = rank = vector<int>(N, 0);
REP(i, N) par[i] = i;
}
int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) par[x] = y;
else par[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
bool same(int x, int y) { return find(x) == find(y); }
};
struct UndirectedGraph
{
using pint = pair<int, int>;
int V; // 頂点数
int E; // 辺の数
int k;
vector<vector<pint>> to;
vector<pint> edges;
vector<int> order, lowlink; // lowlink
vector<bool> isusedforDFS; // 各辺がDFS木に参加しているか
vector<bool> is_art; // 各点が関節点か
vector<vector<int> > bvc_edges; // 二連結成分分解後の全辺の分類
vector<int> num_child;
UndirectedGraph(int V) : V(V), E(0), k(0), to(vector<vector<pint>>(V)) {}
void add_edge(int v1, int v2)
{
to[v1].push_back(pint(v2, E));
to[v2].push_back(pint(v1, E));
edges.push_back(pint(v1, v2));
E++;
}
vector<int> edge_stack;
int root_now;
int _dfs_lowlink(int now, int prev = -1)
{
if (prev == -1) root_now = k;
order[now] = lowlink[now] = k;
k++;
for (auto nxt : to[now]) if (nxt.first != prev)
{
if (order[nxt.first] < order[now]) edge_stack.push_back(nxt.second);
if (order[nxt.first] < 0)
{
isusedforDFS[nxt.second] = 1;
num_child[now] += _dfs_lowlink(nxt.first, now);
lowlink[now] = min(lowlink[now], lowlink[nxt.first]);
if ((order[now] == root_now && order[nxt.first] != root_now+1) ||
(order[now] != root_now && lowlink[nxt.first] >= order[now])) is_art[now] = 1;
if (lowlink[nxt.first] >= order[now])
{
bvc_edges.push_back(vector<int>());
while (1)
{
int edge = edge_stack.back();
int v1 = edges[edge].first;
int v2 = edges[edge].second;
edge_stack.pop_back();
bvc_edges.back().push_back(edge);
if (min(v1, v2) == min(now, nxt.first) && max(v1, v2) == max(now, nxt.first)) break;
}
}
} else lowlink[now] = min(lowlink[now], order[nxt.first]);
}
return num_child[now] + 1;
}
void build_lowlink()
{
order.assign(V, -1);
lowlink.assign(V, -1);
isusedforDFS.assign(E, 0);
is_art.assign(V, false);
bvc_edges.clear();
num_child.assign(V, 0);
for (int i = 0; i < V; i++) if (order[i] < 0) _dfs_lowlink(i);
}
};
int main()
{
int N;
cin >> N;
UndirectedGraph graph(2 * N + 1);
UnionFind uf(2 * N + 1);
map<int, vector<int>> xlst[2];
REP(i, 2 * N + 1)
{
int x, y;
cin >> x >> y;
xlst[0][x - 1].push_back(i);
xlst[1][y - 1].push_back(i);
}
REP(d, 2) for (auto pa : xlst[d])
{
int len = pa.second.size();
REP(i, len - 1) uf.unite(pa.second[i], pa.second[i + 1]);
REP(i, len - 1) graph.add_edge(pa.second[i], pa.second[i + 1]);
REP(i, len - 2) graph.add_edge(pa.second[i], pa.second[i + 2]);
}
graph.build_lowlink();
map<int, int> group_size;
REP(i, 2 * N + 1) group_size[uf.find(i)]++;
int odd = -1;
for (auto pa : group_size) if (pa.second & 1)
{
if (odd < 0) odd = pa.first;
else
{
REP(i, 2 * N + 1) cout << "NG" << endl;
return 0;
}
}
REP(i, 2 * N + 1) {
bool flg = true;
if (odd != uf.find(i)) flg = false;
if (graph.is_art[i])
{
for (auto nxt : graph.to[i]) if (graph.lowlink[nxt.first] > graph.order[i] && graph.isusedforDFS[nxt.second])
{
if (!(graph.num_child[nxt.first] & 1)) flg = false;
}
}
cout << (flg ? "OK" : "NG") << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - みんな仲良し高橋君 |
User |
hitonanode |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4689 Byte |
Status |
WA |
Exec Time |
1022 ms |
Memory |
74220 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 30 |
0 / 70 |
Status |
|
|
|
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 |
821 ms |
58152 KB |
bone_1.txt |
WA |
812 ms |
57768 KB |
bone_2.txt |
WA |
845 ms |
57512 KB |
bone_bubun_0.txt |
AC |
152 ms |
17200 KB |
bone_bubun_1.txt |
AC |
16 ms |
2432 KB |
bone_bubun_2.txt |
AC |
230 ms |
23280 KB |
example_0.txt |
AC |
1 ms |
256 KB |
example_1.txt |
AC |
1 ms |
256 KB |
example_2.txt |
AC |
1 ms |
256 KB |
handmade_0.txt |
AC |
1 ms |
256 KB |
handmade_1.txt |
AC |
1 ms |
256 KB |
handmade_2.txt |
AC |
1 ms |
256 KB |
handmade_3.txt |
AC |
1 ms |
256 KB |
komakai_0.txt |
WA |
922 ms |
56940 KB |
komakai_1.txt |
WA |
930 ms |
59244 KB |
komakai_2.txt |
WA |
897 ms |
58732 KB |
komakai_bubun_0.txt |
WA |
842 ms |
74220 KB |
komakai_bubun_1.txt |
WA |
792 ms |
70380 KB |
komakai_bubun_2.txt |
WA |
813 ms |
70252 KB |
maxrand_0.txt |
AC |
1022 ms |
53484 KB |
maxrand_1.txt |
AC |
998 ms |
53484 KB |
maxrand_bubun_0.txt |
AC |
770 ms |
61036 KB |
maxrand_bubun_1.txt |
AC |
791 ms |
61676 KB |
random_0.txt |
AC |
21 ms |
2048 KB |
random_1.txt |
AC |
502 ms |
31344 KB |
random_bubun_0.txt |
AC |
23 ms |
2560 KB |
random_bubun_1.txt |
WA |
187 ms |
17524 KB |
renket_0.txt |
WA |
864 ms |
59116 KB |
renket_1.txt |
WA |
881 ms |
58860 KB |
smallrand_0.txt |
AC |
2 ms |
256 KB |
smallrand_1.txt |
AC |
2 ms |
256 KB |
smallrand_bubun_0.txt |
AC |
1 ms |
256 KB |
smallrand_bubun_1.txt |
AC |
1 ms |
256 KB |
smallrand_bubun_2.txt |
WA |
1 ms |
256 KB |
square_0.txt |
AC |
658 ms |
66024 KB |
square_1.txt |
AC |
661 ms |
68456 KB |
square_bubun_0.txt |
AC |
643 ms |
68840 KB |
square_bubun_1.txt |
AC |
464 ms |
54892 KB |
supersmall_0.txt |
AC |
1 ms |
256 KB |
supersmall_1.txt |
AC |
1 ms |
256 KB |
threeren_0.txt |
WA |
799 ms |
50412 KB |
threeren_1.txt |
WA |
829 ms |
54124 KB |
treebase_0.txt |
WA |
712 ms |
52076 KB |
treebase_1.txt |
WA |
129 ms |
12276 KB |
treebase_2.txt |
WA |
489 ms |
40556 KB |