Submission #1736055
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define X first #define Y second const int maxn=1e5+10; int n,f[maxn]; set<int> r[maxn],b[maxn]; queue<pair<int,int> > q; int find(int x) {return x==f[x]?x:f[x]=find(f[x]);} int main() { #ifdef h10 freopen("E.in","r",stdin); freopen("E.out","w",stdout); #endif int i,u,v; scanf("%d",&n); for (i=1;i<=n;i++) f[i]=i; for (i=1;i<n;i++) { scanf("%d%d",&u,&v); r[u].insert(v); r[v].insert(u); } for (i=1;i<n;i++) { scanf("%d%d",&u,&v); b[u].insert(v); b[v].insert(u); if (r[u].count(v)) q.push(make_pair(u,v)); } while (!q.empty()) { u=find(q.front().X); v=find(q.front().Y); q.pop(); if (u==v) continue; if (r[u].size()+b[u].size()<r[v].size()+b[v].size()) swap(u,v); set<int>::iterator it; for (it=r[v].begin();it!=r[v].end();it++) { int tmp=find(*it); r[u].insert(tmp); r[tmp].insert(u); if (b[u].count(tmp)) q.push(make_pair(u,tmp)); } for (it=b[v].begin();it!=b[v].end();it++) { int tmp=find(*it); b[u].insert(tmp); b[tmp].insert(u); if (r[u].count(tmp)) q.push(make_pair(u,tmp)); } r[v].clear(); b[v].clear(); f[v]=u; } for (i=2;i<=n;i++) if (find(i)!=find(1)) {puts("NO"); return 0;} puts("YES"); }
Submission Info
Submission Time | |
---|---|
Task | E - Blue and Red Tree |
User | h10 |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 1315 Byte |
Status | AC |
Exec Time | 493 ms |
Memory | 31232 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:21:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&u,&v); ^ ./Main.cpp:31:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&u,&v); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1400 / 1400 | ||||
Status |
|
|
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 | 6 ms | 9600 KB |
in10.txt | AC | 129 ms | 28800 KB |
in11.txt | AC | 433 ms | 31232 KB |
in12.txt | AC | 493 ms | 31232 KB |
in13.txt | AC | 470 ms | 31232 KB |
in14.txt | AC | 488 ms | 31232 KB |
in15.txt | AC | 450 ms | 31232 KB |
in16.txt | AC | 464 ms | 31232 KB |
in17.txt | AC | 469 ms | 31232 KB |
in18.txt | AC | 478 ms | 31232 KB |
in19.txt | AC | 462 ms | 31232 KB |
in2.txt | AC | 6 ms | 9600 KB |
in20.txt | AC | 419 ms | 31232 KB |
in21.txt | AC | 387 ms | 30848 KB |
in22.txt | AC | 374 ms | 30848 KB |
in23.txt | AC | 405 ms | 30848 KB |
in24.txt | AC | 393 ms | 30848 KB |
in25.txt | AC | 427 ms | 30836 KB |
in26.txt | AC | 442 ms | 30976 KB |
in27.txt | AC | 447 ms | 30976 KB |
in28.txt | AC | 420 ms | 30976 KB |
in29.txt | AC | 417 ms | 30976 KB |
in3.txt | AC | 6 ms | 9600 KB |
in30.txt | AC | 437 ms | 30976 KB |
in31.txt | AC | 444 ms | 29056 KB |
in32.txt | AC | 427 ms | 29056 KB |
in33.txt | AC | 423 ms | 29056 KB |
in34.txt | AC | 425 ms | 29056 KB |
in35.txt | AC | 425 ms | 29056 KB |
in36.txt | AC | 414 ms | 29056 KB |
in37.txt | AC | 415 ms | 29056 KB |
in38.txt | AC | 370 ms | 29056 KB |
in39.txt | AC | 411 ms | 29056 KB |
in4.txt | AC | 136 ms | 28800 KB |
in40.txt | AC | 418 ms | 29056 KB |
in41.txt | AC | 487 ms | 29056 KB |
in42.txt | AC | 429 ms | 29056 KB |
in43.txt | AC | 423 ms | 29056 KB |
in44.txt | AC | 432 ms | 29056 KB |
in45.txt | AC | 429 ms | 29056 KB |
in46.txt | AC | 425 ms | 29056 KB |
in47.txt | AC | 398 ms | 29056 KB |
in5.txt | AC | 138 ms | 28800 KB |
in6.txt | AC | 387 ms | 28928 KB |
in7.txt | AC | 146 ms | 28800 KB |
in8.txt | AC | 118 ms | 28800 KB |
in9.txt | AC | 153 ms | 28800 KB |
sample1.txt | AC | 6 ms | 9600 KB |
sample2.txt | AC | 6 ms | 9600 KB |
sample3.txt | AC | 6 ms | 9600 KB |