Submission #598707

#	Time	Username	Problem	Language	Result	Execution time	Memory
598707		alirezasamimi100	Split the Attractions (IOI19_split)	C++17	100 / 100	106 ms	20224 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
using pii = pair<int,int>;

const int N = 1e5 + 10;

int n,a,b,c,sz[N],f[N],dp[N],h[N],np[N],t=1,k,r,l;
vector<int> adj[N],ans;
void dfs(int v, int p){
    f[v]=1;
    sz[v]=1;
    dp[v]=h[v];
    int fl=1;
    for(int u : adj[v]){
        if(u==p) continue;
        if(f[u]) dp[v]=min(dp[v],h[u]);
        else{
            h[u]=h[v]+1;
            dfs(u,v);
            dp[v]=min(dp[v],dp[u]);
            sz[v]+=sz[u];
            if(sz[u]>=a) fl=0;
        }
    }
    if(sz[v]>=a && fl){
        k=sz[v];
        r=v;
        for(int u : adj[v]){
            if(h[u]!=h[v]+1 || dp[u]>=h[v]) continue;
            if(k-sz[u]>=a){
                np[u]=1;
                k-=sz[u];
            }
        }
        if(n-k<a) t=0;
    }
}

void sfd(int v){
    if(l==1 && a){
        a--;
        ans[v]=1;
    }else if(l==2 && b){
        b--;
        ans[v]=2;
    }else{
        ans[v]=3;
    }
    for(int u : adj[v]){
        if(h[u]==h[v]+1 && !np[u]) sfd(u);
    }
}

void solve(int v){
    if(l==1 && b){
        b--;
        ans[v]=2;
    }else if(l==2 && a){
        a--;
        ans[v]=1;
    }else ans[v]=3;
    for(int u : adj[v]){
        if(ans[u]) continue;
        solve(u);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    ::n=n;
    vector<pii> wtf={{a,1},{b,2},{c,3}};
    sort(wtf.begin(),wtf.end());
    a=::a=wtf[0].F;
    b=::b=wtf[1].F;
    c=::c=wtf[2].F;
    ans.resize(n);
    for(int i=0; i<(int)p.size(); i++){
        adj[p[i]].pb(q[i]);
        adj[q[i]].pb(p[i]);
    }
    dfs(0,-1);
    if(!t) return ans;
    if(n-k>=b) l=1;
    else l=2;
    sfd(r);
    solve(0);
    for(int i=0; i<n; i++) ans[i]=wtf[ans[i]-1].S;
    return ans;
}

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