Submission #442704

#	Time	Username	Problem	Language	Result	Execution time	Memory
442704		Dan13llljws	Split the Attractions (IOI19_split)	C++14	40 / 100	139 ms	16112 KiB

split

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0',ch=getchar();}return s*f;}
#define re read()
const int mod = 1e9 + 7, MM = 1e5 + 5;
struct E{int u, v;}e[MM<<1], bad[MM<<1];
int N, tb, cnt, cur, t, rt, top, sz[MM], dsu[MM], w[MM]; vector<int> s, adj[MM]; pair<int,int> ord[3];
int Find(int x){return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);}
void unite(int x, int y){x = Find(x), y = Find(y); sz[y] += sz[x], dsu[x] = y;}
int get_w(int src, int par){
    w[src] = 1;
    for (int v : adj[src])
        if (v != par) w[src] += get_w(v, src);
    return w[src];
}
int get_c(int src, int par){
    for (int v : adj[src])
        if (v != par && w[v] * 2 > N) return get_c(v, src);
    return src;
}
void merge(int src, int par){
    if (par != rt) unite(src, par);
    for (int v : adj[src])
        if (v != par) merge(v, src);
}
void paint(int src, int par){
    if (s[src]) return;
    cnt ? (s[src] = cur, cnt--) : s[src] = ord[2].second;
    for (int v : adj[src])
        if (v != par) paint(v, src);
}
vector<int> find_split(int n, int a, int b, int c, vector<int>p, vector<int>q){
    int m = p.size(); s.resize(N = n);
    for (int i = 0; i < m; i++) e[i] = {q[i], p[i]};
    ord[0] = {a, 1}, ord[1] = {b, 2}, ord[2] = {c, 3};
    sort(ord, ord + 3); iota(dsu, dsu + n, 0);
    for (int i = 0; i < m; i++){
        if (Find(e[i].v) != Find(e[i].u)){
            unite(e[i].v, e[i].u);
            adj[e[i].v].push_back(e[i].u), adj[e[i].u].push_back(e[i].v);
        } else bad[tb++] = e[i];
    } get_w(0, 0), rt = get_c(0, 0), iota(dsu, dsu + n, 0);
    for (int i = 0; i < n; i++) sz[i] = 1;
    for (int v : adj[rt]) merge(v, rt);
//     sort(adj[rt].begin(), adj[rt].end());
//     sort(bad, bad + tb, [&](E x, E y){return min(Find(x.u), Find(x.v)) < min(Find(y.u), Find(y.v));});
    for (int i = 0; i < tb; i++){
        if (bad[i].u == rt || bad[i].v == rt) continue;
        if (sz[Find(bad[i].u)] >= ord[0].first || sz[Find(bad[i].v)] >= ord[0].first) break;
        if (Find(bad[i].u) != Find(bad[i].v)) unite(bad[i].u, bad[i].v);
    }
    int id = -1;
    for (int v : adj[rt])
        if (sz[Find(v)] >= ord[0].first){id = v; break;}
    if (id != -1){
        cnt = ord[0].first, cur = ord[0].second;
        for (int v : adj[rt])
            if (Find(v) == Find(id)) paint(v, rt);
        cnt = ord[1].first, cur = ord[1].second, paint(rt, rt);
    } return s;
}
// int main(){
//     vector<int> a = {8, 9, 6, 3, 3, 3, 7, 7, 2, 4, 5, 3, 9, 5, 0, 0, 6}, b = {9, 6, 7, 8, 4, 1, 0, 3, 6, 1, 9, 2, 3, 1, 5, 1, 8};
//     vector<int> ans = find_split(10, 5, 3, 2, a, b);
//     for(int x : ans) cout << x << ' ';
// }

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36