| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 645130 | s7mon | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
int n, m, a, b, c;
vector<int> adj[N];
namespace sub1{
int va = 0, vb = 1, cnta = 0, cntb = 0;
int sz[N], lab[N], par[N];
void dfs(int u, int pu){
if ( va ) return;
sz[u] = 1;
for (int v : adj[u]) if ( v != pu ){
dfs(v, u);
par[v] = u;
sz[u] += sz[v];
}
bool ck = ( sz[u] >= a );
for (int v : adj[u]) if ( v != pu )
ck &= ( sz[v] < a );
if ( ck ) va = u;
}
void dfsa(int u){
if ( cnta == a ) return;
cnta ++; lab[u] = 1;
// cout << u << ' ' << lab[u] << '\n';
for (int v : adj[u]) if ( v != par[u] && v != vb )
dfsa(v);
}
void dfsb(int u){
if ( cntb == b ) return;
cntb ++; lab[u] = 2;
// cout << u << ' ' << lab[u] << '\n';
for (int v : adj[u]) if ( v != par[u] && v != va )
dfsb(v);
}
void solve(){
dfs(1, 0);
if ( n - sz[va] < a ){
for (int i = 1; i <= n; i ++)
cout << 0 << ' ';
return;
}
else{
if ( sz[va] >= b ) swap(vb, va);
for (int i = 1; i <= n; i ++) lab[i] = 3;
dfsa(va);
dfsb(vb);
for (int i = 1; i <= n; i ++)
cout << lab[i] << ' ';
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if ( fopen("split.inp", "r") ){
freopen("split.inp", "r", stdin);
freopen("split.out", "w", stdout);
}
cin >> n >> m >> a >> b >> c;
for (int i = 1; i <= m; i ++){
int u, v;
cin >> u >> v;
u ++, v ++;
adj[u].pb(v);
adj[v].pb(u);
}
if ( m == n - 1 ) sub1::solve();
return 0;
}