Submission #1141730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141730		onlk97	Split the Attractions (IOI19_split)	C++20	100 / 100	73 ms	17736 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

int dsu[100010];
int prt(int n){
    if (dsu[n]==n) return n;
    return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
    dsu[prt(u)]=dsu[prt(v)];
}
vector <int> g[100010];
int sz[100010];
void dfs(int cur,int prv){
    sz[cur]=1;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs(i,cur);
        sz[cur]+=sz[i];
    }
}
int getcen(int cur,int prv,int n){
    for (int i:g[cur]){
        if (i==prv) continue;
        if (2*sz[i]>n) return getcen(i,cur,n);
    }
    return cur;
}
int belong[100010],siz[100010];
void dfs2(int cur,int prv,int lab){
    belong[cur]=lab;
    siz[lab]++;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs2(i,cur,lab);
    }
}
vector <int> ans;
vector <pair <int,int> > ord;
void complete(int r){
    queue <int> q;
    q.push(r);
    ans[r]=ord[1].second;
    int cnt=1;
    while (cnt<ord[1].first){
        int tp=q.front(); q.pop();
        for (int i:g[tp]){
            if (ans[i]) continue;
            cnt++;
            ans[i]=ord[1].second;
            q.push(i);
            if (cnt==ord[1].first) break;
        }
    }
    for (int i=0; i<ans.size(); i++){
        if (!ans[i]) ans[i]=ord[2].second;
    }
}
vector <int> find_split(int n,int a,int b,int c,vector <int> p,vector <int> q){
    ord.push_back({a,1}); ord.push_back({b,2}); ord.push_back({c,3});
    sort(ord.begin(),ord.end());
    for (int i=0; i<n; i++) dsu[i]=i;
    vector <int> rem[n];
    for (int i=0; i<p.size(); i++){
        if (prt(p[i])==prt(q[i])){
            rem[p[i]].push_back(q[i]);
            rem[q[i]].push_back(p[i]);
            continue;
        }
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
        unn(p[i],q[i]);
    }
    ans.resize(n);
    dfs(0,-1);
    c=getcen(0,-1,n);
    for (int i=0; i<n; i++) belong[i]=-1;
    for (int i:g[c]) dfs2(i,c,i);
    bool done=0;
    for (int i=0; i<n; i++){
        if (siz[i]>=ord[0].first){
            queue <int> q;
            q.push(i);
            ans[i]=ord[0].second;
            int cnt=1;
            while (cnt<ord[0].first){
                int tp=q.front(); q.pop();
                for (int j:g[tp]){
                    if (ans[j]||belong[j]!=belong[i]) continue;
                    q.push(j);
                    ans[j]=ord[0].second;
                    cnt++;
                    if (cnt==ord[0].first) break;
                }
            }
            done=1;
            break;
        }
    }
    if (!done){
        bool visited[n];
        for (int i=0; i<n; i++) visited[i]=0;
        visited[c]=1;
        for (int i=0; i<n; i++){
            if (visited[i]) continue;
            deque <int> q;
            vector <int> vec;
            int cnt=0;
            q.push_back(i);
            while (!q.empty()&&cnt<ord[0].first){
                int tp=q.front(); q.pop_front();
                if (visited[tp]) continue;
                visited[tp]=1;
                vec.push_back(tp); cnt++;
                if (cnt==ord[0].first) break;
                for (int j:g[tp]){
                    if (!visited[j]) q.push_front(j);
                }
                for (int j:rem[tp]){
                    if (!visited[j]) q.push_back(j);
                }
            }
            if (cnt==ord[0].first){
                for (int j:vec) ans[j]=ord[0].second;
                done=1;
                break;
            }
        }
    }
    if (done) complete(c);
    return ans;
}

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