제출 #434162

#제출 시각아이디문제언어결과실행 시간메모리
434162mosiashvililukaHandcrafted Gift (IOI20_gift)C++14
0 / 100
1566 ms54532 KiB
#include "gift.h" #include<bits/stdc++.h> using namespace std; int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,msh[500009],f[500009],NO; vector <int> v[500009]; string S; pair <pair <int, int>, int> p[500009]; void mrg(int q, int w){ q=msh[q];w=msh[w]; if(q==w) return; if(v[q].size()<v[w].size()) swap(q,w); for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){ msh[(*it)]=q; v[q].push_back((*it)); } } void mrg2(int q, int w){ q=msh[q];w=msh[w]; if(q==w){ if(f[q]==f[w]){ NO=1;return; } return; } if(v[q].size()<v[w].size()) swap(q,w); for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){ msh[(*it)]=q; f[(*it)]^=1; } } int construct(int Nn, int Rr, std::vector<int> Aa, std::vector<int> Bb, std::vector<int> Xx) { a=Nn;tes=Rr; for(t=1; t<=tes; t++){ p[t].first.first=Aa[t-1]+1;p[t].first.second=Bb[t-1]+1; p[t].second=Xx[t-1]; } for(i=1; i<=a; i++){ msh[i]=i;f[i]=0; v[i].push_back(i); } sort(p+1,p+tes+1); zx=0; for(t=1; t<=tes; t++){ if(p[t].second==2) continue; if(zx<p[t].first.first){ zx=p[t].first.second; for(i=p[t].first.second; i>p[t].first.first; i--){ mrg(i,i-1); } }else{ for(i=p[t].first.second; i>zx; i--){ mrg(i,i-1); } } } NO=0; for(t=1; t<=tes; t++){ if(p[t].second==1) continue; mrg2(p[t].first.first,p[t].first.second); if(NO==1){ return 0; } } for(i=1; i<=a; i++){ if(f[i]==0){ S+="R"; }else{ S+="B"; } } craft(S); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...