Submission #526408

#	Time	Username	Problem	Language	Result	Execution time	Memory
526408		byunjaewoo	Split the Attractions (IOI19_split)	C++17	100 / 100	179 ms	39304 KiB

split

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pp=pair<int, int>;
 
const int Nmax=200010;
int N, M, a, b, c, Cent, G[Nmax], S[Nmax], T[Nmax], P[Nmax], Sz[Nmax], ans[Nmax];
int A, B, C, ap, bp, cp;
bool visited[Nmax], chk[Nmax];
vector<int> adj[Nmax], mst[Nmax], V[Nmax], W[Nmax];
vector<pp> E;
 
int Find(int u) {return G[u]?G[u]=Find(G[u]):u;}
bool Union(int u, int v) {
    u=Find(u), v=Find(v);
    if(u==v) return false;
    G[u]=v;
    return true;
}
 
void DFS_Size(int curr, int prev) {
    S[curr]=1;
    for(int next:mst[curr]) if(next!=prev) {
        DFS_Size(next, curr);
        S[curr]+=S[next];
    }
}
 
int DFS_Centroid(int curr, int prev) {
    for(int next:mst[curr]) if(next!=prev) {
        if(S[next]>N/2) return DFS_Centroid(next, curr);
    }
    return curr;
}
 
void DFS_Compress(int curr, int c) {
    P[curr]=c, S[curr]=visited[curr]=1;
    W[c].push_back(curr);
    for(int next:mst[curr]) if(!visited[next]) {
        DFS_Compress(next, c);
        S[curr]+=S[next];
    }
}

void DFS_Compressed(int curr, int &sum) {
    sum+=T[curr];
    chk[curr]=1;
    for(int next:V[curr]) if(!chk[next]) DFS_Compressed(next, sum);
}
 
void DFS_DeleteCnt(int curr, int &cnt, int c) {
    ans[curr]=c; cnt--;
    if(!cnt) return;
    for(int next:mst[curr]) if(!ans[next]) {
        DFS_DeleteCnt(next, cnt, c);
        if(!cnt) return;
    }
}
 
void DFS_EraseSum(int curr, int &sum) {
    chk[curr]=1;
    sum+=T[curr];
    for(int i:W[curr]) ans[i]=-1;
    if(sum>=A) return;
    for(int next:V[curr]) if(!chk[next]) {
        DFS_EraseSum(next, sum);
        if(sum>=A) return;
    }
}

void DFS_Delete(int curr, int &cnt) {
    visited[curr]=1, cnt--, ans[curr]=ap;
    if(!cnt) return;
    for(int next:adj[curr]) if(ans[next]==-1 && !visited[next]) {
        DFS_Delete(next, cnt);
        if(!cnt) return;
    }
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    N=n, M=p.size();
    A=min({a, b, c}), C=max({a, b, c}), B=a+b+c-A-C;
    ap=(a==A)?1:((b==A)?2:3), cp=(c==C)?3:((b==C)?2:1), bp=6-ap-cp;
    for(int i=1; i<=M; i++) {
        int u, v; u=p[i-1], v=q[i-1];
        u++, v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E.push_back({u, v});
    }
    for(pp i:E) {
        if(Union(i.x, i.y)) {
            mst[i.x].push_back(i.y);
            mst[i.y].push_back(i.x);
        }
    }
    DFS_Size(1, 0);
    Cent=DFS_Centroid(1, 0);
    int cnt=0;
    visited[Cent]=1;
    for(int i:mst[Cent]) {
        DFS_Compress(i, ++cnt);
        if(S[i]>=A) {
            int tmp=A;
            ans[Cent]=bp;
            DFS_DeleteCnt(i, tmp, ap);
            tmp=B;
            DFS_DeleteCnt(Cent, tmp, bp);
            vector<int> t;
            for(int i=1; i<=N; i++) {
                if(!ans[i]) ans[i]=cp;
                t.push_back(ans[i]);
            }
            return t;
        }
        T[cnt]=S[i];
    }
    for(pp i:E) if(P[i.x]!=P[i.y] && P[i.x] && P[i.y]) {
        V[P[i.x]].push_back(P[i.y]);
        V[P[i.y]].push_back(P[i.x]);
    }
    for(int i=1; i<=cnt; i++) {
        sort(V[i].begin(), V[i].end());
        V[i].erase(unique(V[i].begin(), V[i].end()), V[i].end());
    }
    for(int i=1; i<=cnt; i++) if(!chk[i]) {
        int siz=0;
        DFS_Compressed(i, siz);
        if(siz>=A) {
            int sum=0;
            fill(chk+1, chk+cnt+1, 0);
            DFS_EraseSum(i, sum);
            fill(visited+1, visited+N+1, 0);
            sum=A;
            DFS_Delete(W[i][0], sum);
            sum=B;
            DFS_DeleteCnt(Cent, sum, bp);
            vector<int> t;
            for(int j=1; j<=N; j++) {
                if(ans[j]!=ap && ans[j]!=bp) ans[j]=cp;
                t.push_back(ans[j]);
            }
            return t;
        }
    }
    vector<int> t(N, 0);
    return t;
}

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