| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 823012 | vjudge1 | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "split.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
int cnt ;
bool us[N + 1] ;
vector<int> res, komp, v[N + 1] ;
void ultra_clear()
{
for(int i = 0 ; i < N ; i++)
us[i] = 0 ;
}
void dfs(int city)
{
cnt++ ;
us[city] = 1 ;
for(int i : v[city])
{
if(us[i])
continue ;
dfs(i) ;
}
}
void dfs_save(int city)
{
us[city] = 1 ;
komp.push_back(city) ;
for(int i : v[city])
{
if(us[i])
continue ;
dfs_save(i) ;
}
}
void dfs_color(int city, int color, int& cnt)
{
if(cnt)
{
res[city] = color ;
cnt-- ;
}
us[city] = 1 ;
for(int i : v[city])
{
if(us[i] || !cnt)
continue ;
dfs_color(i, color, cnt) ;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
bool flag1 = 0, flag2 = 0 ;
for(int i = 0 ; i < n ; i++)
res.push_back(0) ;
int m = fr.size() ;
for(int i = 0 ; i < m ; i++)
{
v[fr[i]].push_back(to[i]) ;
v[to[i]].push_back(fr[i]) ;
if(v[to[i]].size() > 2 || v[fr[i]].size() > 2)
flag1 = 1 ;
}
if(!flag1)
{
vector<pair<int, int>> abu = {{a, 1}, {b, 2}, {c, 3}} ;
sort(abu.begin(), abu.end()) ;
for(int i = 0 ; i < n ; i++)
{
if(us[i] || v[i].size() == 2)
continue ;
cnt &= 0 ;
dfs(i) ;
cout<<cnt<<' '<<i << '\n' ;
if(cnt >= abu[0].fi + abu[1].fi)
{
ultra_clear() ;
dfs_save(i) ;
for(int j : komp)
{
if(abu[0].fi)
{
res[j] = abu[0].se ;
abu[0].fi-- ;
continue ;
}
if(abu[1].fi)
{
res[j] = abu[1].se ;
abu[1].fi-- ;
}
}
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = abu[2].se ;
return res ;
}
}
for(int i = 0 ; i < n ; i++)
{
if(us[i])
continue ;
cnt &= 0 ;
dfs(i) ;
if(cnt >= abu[0].fi + abu[1].fi)
{
ultra_clear() ;
dfs_save(i) ;
for(int j : komp)
{
if(abu[0].fi)
{
abu[0].fi-- ;
res[j] = abu[0].se ;
continue ;
}
if(abu[1].fi)
{
abu[1].fi-- ;
res[j] = abu[1].se ;
}
}
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = abu[2].se ;
return res ;
}
}
//случаи когда мы две группы умещаем в одной компоненте
ultra_clear() ;
int ch1 = -1, ch2 = -1 ;
for(int i = 0 ; i < n ; i++)
{
if(us[i])
continue ;
cnt &= 0 ;
dfs(i) ;
if(cnt >= abu[1].fi && ch2 == -1)
ch2 = i ;
else
{
if(cnt <= abu[0].fi && ch1 == -1)
ch1 = i ;
}
}
if(ch1 != -1 && ch2 != -1)
{
ultra_clear() ;
dfs_color(ch1, abu[0].se, abu[0].fi) ;
dfs_color(ch2, abu[1].se, abu[1].fi) ;
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = abu[2].se ;
}
return res ;
}
if(a == 1)
{
int ind ;
for(int i = 0 ; i < n ; i++)
{
if(us[i])
continue ;
cnt = 0 ;
dfs(i) ;
if(cnt >= min(b, c))
{
ind = i ;
flag2 = 1 ;
}
}
if(!flag2)
return res ;
else
{
ultra_clear() ;
if(b <= c)
dfs_color(ind, 2, b) ;
else
dfs_color(ind, 3, c) ;
for(int i = 0 ; i < n ; i++)
if(!res[i])
{
if(a)
{
res[i] = 1 ;
a &= 0 ;
}
else
{
if(b)
res[i] = 2 ;
else
res[i] = 3 ;
}
}
}
return res ;
}
return res ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
int n, a, b, c, m ;
cin >> n >> m >> a >> b >> c ;
vector<int> fr(m), to(m) ;
for(int i = 0 ; i < m ; i++)
cin >> fr[i] >> to[i] ;
vector<int> ans = find_split(n, a, b, c, fr, to) ;
for(int i : ans)
cout << i << ' ' ;
return 0 ;
}