| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 281622 | Saacoota | 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>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
#define LL unsigned long long
#define uint unsigned int
#define pb push_back
#define eb emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "SPLIT"
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int oo = 0x3f;
int n , m , res[200010] , chl[200010] , out[200010] , s[200010] , in[200010];
int cnt , tim , ans , ty1 , ty2;
ii a[4];
bool p[200010] , ok[200010] , vs[200010] , fin[200010] , moc[200010];
vector < int > g[200010] , adj[200010] , wy;
///--------------------------
void DFS(int u) {
tim++;
in[u] = tim;
for (auto v : g[u])
if (!in[v]) {
adj[u].pb(v);
DFS(v);
}
out[u] = tim;
}
///--------------------------
void GO(int u) {
for (auto v : adj[u]) {
GO(v);
chl[u] += chl[v];
}
chl[u]++;
}
///--------------------------
void CAL(int u) {
if (chl[u] < a[1].fi) return;
if (ans != 0) return;
for (auto v : adj[u]) {
CAL(v);
if (chl[v] >= a[1].fi) ok[u] = true;
}
s[u] = n - chl[u];
if (!ok[u]) ans = u;
}
///--------------------------
void ANS(int u) {
for (auto v : g[u]) {
if (in[v] < in[ans]) p[u] = true;
}
for (auto v : adj[u]) {
ANS(v);
if (p[v]) p[u] = true;
}
}
///--------------------------
void RES(int u) {
if (s[u] >= a[1].fi) return;
for (auto v : adj[u]) {
if (p[v]) {
wy.pb(v);
s[u] += chl[v];
}
if (s[v] >= a[1].fi) break;
}
}
///--------------------------
void KQ(int u) {
if (cnt >= a[ty1].fi) return;
cnt++;
res[u] = a[ty1].se;
for (auto v : adj[u])
if (!fin[v]) {
KQ(v);
}
}
///--------------------------
void DI(int u) {
if (res[u] != 0) return;
if (cnt >= a[ty2].fi) return;
cnt++;
res[u] = a[ty2].se;
for (auto v : g[u]) DI(v);
}
///--------------------------
void readf() {
cin >> n >> m;
for (int i = 1 ; i <= 3 ; ++i) {
cin >> a[i].fi;
a[i].se = i;
}
sort(a + 1 , a + 3 + 1);
for (int i = 1 ; i <= m ; ++i) {
int u , v;
cin >> u >> v;
u++;++v;
g[u].pb(v);
g[v].pb(u);
}
}
///--------------------------
void solve() {
DFS(1);
GO(1);
CAL(1);
if (ans == 0) {
for (int i = 1 ; i <= n ; ++i) cout << 0 << ' ';
exit(0);
}
ANS(ans);
RES(ans);
//cout << ans << '\n';
if (s[ans] < a[1].fi) {
for (int i = 1 ; i <= n ; ++i)
cout << 0 << ' ';
exit(0);
}
for (auto x : wy) fin[x] = true;
if (s[ans] >= a[2].fi) {
ty1 = 1;
ty2 = 2;
} else {
ty1 = 2;
ty2 = 1;
}
KQ(ans);
cnt = 0;
for (int i = 1 ; i <= n ; ++i)
if (res[i] == 0) {
DI(i);
break;
}
for (int i = 1 ; i <= n ; ++i)
if (res[i] == 0) cout << a[3].se << ' ';
else cout << res[i] << ' ';
}
///--------------------------
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
readf();
solve();
}