Submission #1357534
Source Code Expand
#include<stdio.h> #include<assert.h> #include<vector> #include<string.h> #include<algorithm> #include<memory.h> #include<cmath> #include<string> #include<iostream> #include<set> #include<unordered_set> #include<map> #include<queue> #include<functional> #include<list> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double, double> pdd; typedef tuple<int,int,int> t3; const int MX = 400005; const int MM = 1000000007; int N, M, a, b; vector<pii> G[MX]; int vst[MX], t, low[MX], cnt[MX]; int ans[MX]; vector<int> X; void dfs(int x, int p = 0){ vst[x] = ++t; low[x] = t; for(pii e : G[x]){ int c = e.first, d = e.second; if( c == p ); else if( vst[c] ){ cnt[x]++; low[x] = min(low[c], low[x]); X.push_back(d); } else{ dfs(c, x); cnt[x] += cnt[c] + 2; low[x] = min(low[x], low[c]); if( vst[x] >= low[c] || cnt[c]/2 % 2 == 0 ) X.push_back(d); } } } int main() { scanf("%d", &N); for(int i = 1; i <= 2*N+1; i++){ ans[i] = 0; scanf("%d%d", &a, &b); G[a*2].emplace_back(b*2|1, i); G[b*2|1].emplace_back(a*2, i); } int p = 0; for(int i = 1; i <= 4*N+3; i++){ X.clear(); if( vst[i] == 0 ){ dfs(i); cnt[i]; if( cnt[i]/2%2 == 1){ p++; for(int c : X) ans[c] = 1; } } } if( p >= 2 ) for(int i = 1; i <= 2*N+1; i++) ans[i] = 0; else if( p == 0 ) for(int i = 1; i <= 2*N+1; i++) ans[i] = 1; for(int i = 1; i <= 2*N+1; i++) printf("%s\n", ans[i]? "OK":"NG"); }
Submission Info
Submission Time | |
---|---|
Task | D - みんな仲良し高橋君 |
User | zigui |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1567 Byte |
Status | AC |
Exec Time | 111 ms |
Memory | 27768 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:57:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^ ./Main.cpp:60:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 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 | AC | 89 ms | 24820 KB |
bone_1.txt | AC | 87 ms | 24820 KB |
bone_2.txt | AC | 93 ms | 24820 KB |
bone_bubun_0.txt | AC | 21 ms | 17400 KB |
bone_bubun_1.txt | AC | 7 ms | 14208 KB |
bone_bubun_2.txt | AC | 29 ms | 18680 KB |
example_0.txt | AC | 5 ms | 13824 KB |
example_1.txt | AC | 5 ms | 13824 KB |
example_2.txt | AC | 5 ms | 13824 KB |
handmade_0.txt | AC | 5 ms | 13824 KB |
handmade_1.txt | AC | 5 ms | 13824 KB |
handmade_2.txt | AC | 5 ms | 13824 KB |
handmade_3.txt | AC | 5 ms | 13824 KB |
komakai_0.txt | AC | 108 ms | 26616 KB |
komakai_1.txt | AC | 98 ms | 26104 KB |
komakai_2.txt | AC | 111 ms | 27128 KB |
komakai_bubun_0.txt | AC | 92 ms | 27768 KB |
komakai_bubun_1.txt | AC | 88 ms | 26356 KB |
komakai_bubun_2.txt | AC | 88 ms | 26100 KB |
maxrand_0.txt | AC | 104 ms | 24192 KB |
maxrand_1.txt | AC | 103 ms | 24192 KB |
maxrand_bubun_0.txt | AC | 97 ms | 27636 KB |
maxrand_bubun_1.txt | AC | 102 ms | 27640 KB |
random_0.txt | AC | 7 ms | 14208 KB |
random_1.txt | AC | 54 ms | 20096 KB |
random_bubun_0.txt | AC | 8 ms | 14464 KB |
random_bubun_1.txt | AC | 28 ms | 18304 KB |
renket_0.txt | AC | 101 ms | 26360 KB |
renket_1.txt | AC | 104 ms | 26232 KB |
smallrand_0.txt | AC | 5 ms | 13824 KB |
smallrand_1.txt | AC | 5 ms | 13824 KB |
smallrand_bubun_0.txt | AC | 5 ms | 13824 KB |
smallrand_bubun_1.txt | AC | 5 ms | 13824 KB |
smallrand_bubun_2.txt | AC | 5 ms | 13824 KB |
square_0.txt | AC | 56 ms | 21620 KB |
square_1.txt | AC | 57 ms | 21632 KB |
square_bubun_0.txt | AC | 56 ms | 21628 KB |
square_bubun_1.txt | AC | 43 ms | 21372 KB |
supersmall_0.txt | AC | 5 ms | 13824 KB |
supersmall_1.txt | AC | 5 ms | 13824 KB |
threeren_0.txt | AC | 99 ms | 23932 KB |
threeren_1.txt | AC | 95 ms | 24824 KB |
treebase_0.txt | AC | 75 ms | 23796 KB |
treebase_1.txt | AC | 20 ms | 16384 KB |
treebase_2.txt | AC | 56 ms | 21496 KB |