| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 879231 | Tam_theguide | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, res[N];
vector<int> adj[N], adu[N];
using pii = pair<int, int>;
#define fi first
#define se second
pii x[5];
/// Tree prop:
#define pb push_back
int cnt, low[N], in[N], pa[N], sz[N];
void cmin(int &x, int y){x = min(x, y);}
void dfs(int p, int u){
pa[u] = p; sz[u] = 1;
low[u] = in[u] = ++cnt;
for (auto c: adj[u]){
if (in[c]) cmin(low[u], in[c]);
else{
dfs(u, c);
adu[u].pb(c); sz[u] += sz[c];
cmin(low[u], low[c]);
}
}
}
bool stop = false;
bool nwrip[N];
map<int, bool> rip;
int cntco;
void dfs_co1(int u, int co){
if (cntco < x[co].fi){
res[u] = x[co].se;
cntco++;
nwrip[u] = true;
}
for (auto c: adu[u])
if (!rip[c]) dfs_co1(c, co);
}
bool vis[N];
void dfs_co2(int u, int co){
vis[u] = true;
if (cntco < x[co].fi){
res[u] = x[co].se;
cntco++;
}
for (auto c: adj[u])
if (res[c] == x[3].se && !vis[c]) dfs_co2(c, co);
}
void dfs2(int u){
if (stop) return;
bool asmr = true;
for (auto c: adu[u])
asmr &= (sz[c] < x[1].fi);
if (asmr && sz[u] >= x[1].fi){
rip.clear();
int num = n - sz[u];
for (auto c: adu[u]){
if (low[c] < in[u] && num < x[1].fi){
num += sz[c]; rip[c] = true;
}
}
if (num >= x[1].fi){
for (int i = 1; i <= n; i++)
res[i] = x[3].se;
if (num >= x[2].fi){
dfs_co1(u, 1);
cntco = 0;
dfs_co2(pa[u], 2);
}else{
dfs_co1(u, 2);
cntco = 0;
dfs_co2(pa[u], 1);
}
stop = true;
}
}
for (auto c: adu[u])
dfs2(c);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= 3; i++)
cin >> x[i].fi, x[i].se = i;
sort(x + 1, x + 4);
for (int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
u++; v++;
adj[u].pb(v); adj[v].pb(u);
}
dfs(0, 1);
dfs2(1);
for (int i = 1; i <= n; i++) cout << res[i] << " ";
}