Submission #1776552
Source Code Expand
#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <set> const int maxn=1e5+10; typedef std::pair<int,int> pii; typedef std::set<int>::iterator tit; std::set<int> ed[2][maxn]; std::set<pii> todo; int fa[maxn]; void addedge(int id,int u,int v) { ed[id][u].insert(v); ed[id][v].insert(u); if(ed[id^1][u].find(v)!=ed[id^1][u].end()) todo.insert(std::make_pair(u,v)); } void rename(int u,int v) { fa[u]=v; for(tit it=ed[0][u].begin();it!=ed[0][u].end();it++) { ed[0][*it].erase(u); addedge(0,v,*it); } for(tit it=ed[1][u].begin();it!=ed[1][u].end();it++) { ed[1][*it].erase(u); addedge(1,v,*it); } ed[0][u].clear(); ed[1][u].clear(); } int getf(int x) { return fa[x]==x?x:fa[x]=getf(fa[x]); } int n; int read() { char ch=getchar(); int x=0,f=1; while(!isdigit(ch)) { f=(ch=='-'?-f:f); ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return f<0?-x:x; } int main() { n=read(); for(int i=1;i<n;i++) { int u,v; u=read();v=read(); addedge(0,u,v); } for(int i=1;i<n;i++) { int u,v; u=read();v=read(); addedge(1,u,v); } int cnt=0; for(int i=1;i<=n;i++) fa[i]=i; while(todo.size()>0) { pii cur=*todo.begin(); todo.erase(todo.begin()); cur.first=getf(cur.first); cur.second=getf(cur.second); ed[0][cur.first].erase(cur.second); ed[1][cur.first].erase(cur.second); ed[0][cur.second].erase(cur.first); ed[1][cur.second].erase(cur.first); if(ed[0][cur.first].size()+ed[1][cur.first].size()<ed[0][cur.second].size()+ed[1][cur.second].size()) rename(cur.first,cur.second); else rename(cur.second,cur.first); cnt++; } if(cnt==n-1)puts("YES");else puts("NO"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Blue and Red Tree |
User | lkmcfj |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2040 Byte |
Status | WA |
Exec Time | 300 ms |
Memory | 30848 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 5 ms | 9600 KB |
in10.txt | AC | 92 ms | 28800 KB |
in11.txt | WA | 173 ms | 30592 KB |
in12.txt | WA | 182 ms | 30464 KB |
in13.txt | WA | 178 ms | 30592 KB |
in14.txt | WA | 174 ms | 30592 KB |
in15.txt | WA | 172 ms | 30464 KB |
in16.txt | WA | 175 ms | 30592 KB |
in17.txt | WA | 183 ms | 30592 KB |
in18.txt | WA | 180 ms | 30592 KB |
in19.txt | WA | 179 ms | 30592 KB |
in2.txt | AC | 5 ms | 9600 KB |
in20.txt | WA | 175 ms | 30592 KB |
in21.txt | AC | 175 ms | 30336 KB |
in22.txt | AC | 174 ms | 30336 KB |
in23.txt | AC | 177 ms | 30336 KB |
in24.txt | AC | 171 ms | 30336 KB |
in25.txt | AC | 173 ms | 30336 KB |
in26.txt | AC | 180 ms | 30592 KB |
in27.txt | WA | 180 ms | 30464 KB |
in28.txt | WA | 183 ms | 30592 KB |
in29.txt | WA | 200 ms | 30592 KB |
in3.txt | AC | 5 ms | 9600 KB |
in30.txt | WA | 190 ms | 30464 KB |
in31.txt | WA | 272 ms | 28800 KB |
in32.txt | WA | 273 ms | 30848 KB |
in33.txt | WA | 273 ms | 28800 KB |
in34.txt | WA | 269 ms | 28800 KB |
in35.txt | WA | 295 ms | 28800 KB |
in36.txt | WA | 88 ms | 28800 KB |
in37.txt | WA | 272 ms | 28800 KB |
in38.txt | WA | 208 ms | 28800 KB |
in39.txt | WA | 205 ms | 28800 KB |
in4.txt | AC | 92 ms | 28800 KB |
in40.txt | WA | 217 ms | 28800 KB |
in41.txt | AC | 292 ms | 28800 KB |
in42.txt | AC | 279 ms | 28800 KB |
in43.txt | AC | 279 ms | 28800 KB |
in44.txt | AC | 90 ms | 28800 KB |
in45.txt | AC | 300 ms | 28800 KB |
in46.txt | AC | 244 ms | 28800 KB |
in47.txt | WA | 234 ms | 28800 KB |
in5.txt | AC | 112 ms | 28800 KB |
in6.txt | AC | 236 ms | 28800 KB |
in7.txt | AC | 105 ms | 28800 KB |
in8.txt | AC | 108 ms | 28800 KB |
in9.txt | AC | 106 ms | 28800 KB |
sample1.txt | AC | 5 ms | 9600 KB |
sample2.txt | AC | 5 ms | 9600 KB |
sample3.txt | AC | 5 ms | 9600 KB |