| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1322284 | phungmanager0 | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 KiB |
#include "split.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x) (std::isinf(x))
#define IS_NAN(x) (std::isnan(x))
#define fi first
#define se second
#define int long long
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div ___div
#define prev ___prev
#define next ___next
#define left ___leftc
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __Im_sogood__ main()
#define __builtin_popcount __builtin_popcountll
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 1e18;
int n, m, a, b, c; vector<int> p, q;
void read_fake_input() {
cin >> n >> m >> a >> b >> c; p.resize(m); q.resize(m);
REP(i, m) cin >> p[i] >> q[i]; //REP(i, m) cin >> q[i];
}
struct DisjointSet {
vector<int> par, Sz;
void init(int n) { par.resize(n + 5); Sz.resize(n + 5);
REP(i, n) par[i] = i, Sz[i] = 1;}
int get(int u) { return (par[u] == u ? u : par[u] = get(par[u])); }
bool merge(int u, int v) {
u = get(u); v = get(v);
if(u == v) return false;
if(Sz[u] < Sz[v]) swap(u, v);
par[v] = u; Sz[u] += Sz[v];
return true;
}
};
struct updateDisjointSet {
vector<int> par, Sz, total_val; void init(int n) { par.resize(n + 5); Sz.resize(n + 5); total_val.resize(n + 5);
REP(i, n) par[i] = i, Sz[i] = 1; }
void update(int idx, int W) { total_val[idx] = W; }
int get(int u) { return (u == par[u] ? u : par[u] = get(par[u])); }
void merge(int u, int v) {
u = get(u); v = get(v); if(Sz[u] < Sz[v]) swap(u, v);
par[v] = u; Sz[u] += Sz[v]; total_val[u] += total_val[v];
}
};
bool cmp(const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; }
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<pair<int, int>> cmp_list = {{a, 1}, {b, 2}, {c, 3}}; sort(ALL(cmp_list), cmp);
//FORE(it, cmp_list) cout << (*it).second << endl;
DisjointSet dsu, compress; dsu.init(n); compress.init(n);
vector<int> res(n), h(n), Sz(n); vector<pair<int, int>> edges, edgesspanningtree, otheredges;
REP(i, (int)p.size()) {
edges.push_back({p[i], q[i]}); //cout << edges.back().first << " " << edges.back().second << endl;
}
vector<vector<int>> spanningtree, g; spanningtree.resize(n + 5); g.resize(n + 5); int u = 0, v = 0;
FORE(it, edges) {
u = (*it).first; v = (*it).second; if(dsu.merge(u, v)) {
spanningtree[u].push_back(v); spanningtree[v].push_back(u);
//cout << u << " " << v << endl;
edgesspanningtree.push_back({u, v});
} else otheredges.push_back({u, v});
g[u].push_back(v); g[v].push_back(u);
}
function<void(int, int)> DFS = [&](int u, int p) {
Sz[u] = 1;
FORE(it, spanningtree[u]) if((*it) != p) {
h[(*it)] = h[u] + 1; DFS((*it), u); Sz[u] += Sz[*it];
}
};
function<int(int, int)> FindCentroid = [&](int u, int p) {
FORE(it, spanningtree[u]) if((*it) != p && Sz[(*it)] > n / 2) {
return FindCentroid(*it, u);
}
return u;
};
DFS(0, -1); int centroid = FindCentroid(0, -1); //cout << centroid << endl;
FORE(it, edgesspanningtree) {
if((*it).first != centroid && (*it).second != centroid) {
compress.merge((*it).first, (*it).second);
}
}
vector<pair<int, int>> points; REP(i, n) if(i == compress.get(i)) {
points.push_back({i, 0}); //cout << i << endl;
}
for(auto &[x, y] : points) y = compress.Sz[compress.get(x)]; int cnt = 0;
//cout << "debug points: " << "\n"; FORE(it, points) cout << (*it).first << " " << (*it).second << endl;
function<void(int, int)> DFS_Fill = [&](int u, int p) {
if(cnt == cmp_list[0].first) return;
res[u] = cmp_list[0].second; /*cout << "dbg: " << u << endl;*/ cnt++; if(cnt == cmp_list[0].first) return;
FORE(it, spanningtree[u]) if((*it) != p) {
if(cnt == cmp_list[0].first) return;
DFS_Fill(*it, u);
if(cnt== cmp_list[0].first) return;
}
};
bool check = false; int idx_comp = -1;
FORE(it, points) {
if((*it).second >= cmp_list[0].first && (*it).first != centroid) {
check = true; idx_comp = (*it).first; break; }
}
if(check) {
//cout << "dbg";
int next_idx = -1;
FORE(it, spanningtree[centroid]) if(compress.get(*it) == idx_comp) { next_idx = (*it); break; }
else if((*it) == idx_comp) { next_idx = idx_comp; break; }
if(next_idx == -1) return res;
//cout << "dbg: " << next_idx << endl;
//cout << idx_comp << endl;
DFS_Fill(next_idx, centroid); queue<int> q; q.push(centroid); cnt = 0; while(q.size()) {
int u = q.front(); q.pop(); cnt++; res[u] = cmp_list[1].second;
//cout << "debug bfs: " << u << endl;
if(cnt == cmp_list[1].first) break;
FORE(it, spanningtree[u]) if(res[*it] == 0) {
q.push(*it);// cout << "debug bfs: " << (*it) << endl;
}
}
REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
} else {
updateDisjointSet compute; compute.init(n);
// compress is a forest
REP(i, (int)points.size()) compute.update(points[i].first, points[i].second);
vector<vector<int>> newGraph(n + 1); vector<int> Weight(n + 1);
FORE(it, points) Weight[(*it).first] = (*it).second;
int first_comp = -1, second_comp = -1;
FORE(it, otheredges) {
if((*it).first == centroid || (*it).second == centroid) continue;
first_comp = compress.get((*it).first); second_comp = compress.get((*it).second);
if(first_comp != second_comp) {
newGraph[first_comp].push_back(second_comp); newGraph[second_comp].push_back(first_comp);
compute.merge(first_comp, second_comp);
//cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
}
//cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
}
bool check_ans = false; int start_bfs = 0; vector<bool> check(n + 1), allow(n + 1);
FORE(it, points) if(compute.total_val[compute.get((*it).first)] >= cmp_list[0].first) { check_ans = true; start_bfs = (*it).first; break; }
if(check_ans) {
//cout << "dbg";
queue<int> q; int sumWeight = 0;
q.push(start_bfs); while(q.size()) {
int u = q.front(); q.pop(); if(check[u]) continue; check[u] = true;
sumWeight += Weight[u]; if(sumWeight >= cmp_list[0].first) break;
else {
FORE(it, newGraph[u]) if(!check[(*it)]) q.push(*it);
}
}
REP(i, n) if(check[compress.get(i)]) allow[i] = true; allow[centroid] = false;
while(q.size()) q.pop(); q.push(start_bfs); int cnt = 0; while(q.size()) {
int u = q.front(); q.pop();
if(res[u] != 0) continue; res[u] = cmp_list[0].second; cnt++; if(cnt == cmp_list[0].first) break;
else {
FORE(it, g[u]) if(res[*it] == 0 && allow[*it]) q.push(*it);
}
} while(q.size()) q.pop(); q.push(centroid); cnt = 0; while(q.size()) {
int u = q.front(); q.pop(); if(res[u] != 0) continue; cnt++; res[u] = cmp_list[1].second;
if(cnt == cmp_list[1].first) break;
FORE(it, spanningtree[u]) if(res[*it] == 0) {
q.push(*it);
}
}
REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
}
}
//cout << "dbg";
return res;
}
/*void solve() {
read_fake_input(); vector<int> res = find_split(n, a, b, c, p, q);
REP(i, n) cout << res[i] << " ";
}
__Im_sogood__{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}*/