# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
147473 | 2019-08-29T16:18:16 Z | mosiashvililuka | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; int z,x,d,e,ka[10],zx,m,la[100009]; vector <int> pas,v[100009]; bool bo[100009]; void dfs(int w){ if(ka[zx]==0) return; bo[w]=1; pas[w]=zx; ka[zx]--; if(ka[zx]==0) return; for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){ if(bo[(*it)]==1) continue; dfs((*it)); if(ka[zx]==0) return; } } int main(){ int n,a,b,c; vector <int> p,q; cin>>n>>m>>a>>b>>c; pas.resize(n); ka[1]=a; ka[2]=b; ka[3]=c; zx=0; for(int h=0; h<m; h++){ cin>>d>>e; p.push_back(d); q.push_back(e); v[p[h]].push_back(q[h]); v[q[h]].push_back(p[h]); } zx=0; for(d=0; d<n; d++){ if(v[d].size()!=1) continue; if(bo[d]==0){ zx++; dfs(d); } } if(zx!=0){ for(d=0; d<n; d++) if(pas[d]==0) pas[d]=3; }else{ zx=0; for(d=0; d<n; d++){ if(bo[d]==0){ zx++; dfs(d); } } } for(int h=0; h<n; h++) cout<<pas[h]<<" "; }