Submission #1203827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203827		Aviansh	Split the Attractions (IOI19_split)	C++20	22 / 100	60 ms	14284 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

int rt;

void dfs(int st, vector<int>g[], int sz[], int a, int b, int c, int p){
    for(int i : g[st]){
        if(sz[i]>=a&&sz[st]-sz[i]>=min(b,c)){
            rt=st;
        }
        if(sz[i]>=b&&sz[st]-sz[i]>=min(a,c)){
            rt=st;
        }
        if(sz[i]>=c&&sz[st]-sz[i]>=min(b,a)){
            rt=st;
        }
        if(i==p)
            continue;
        int n = sz[st];
        int o = sz[i];
        sz[st]-=sz[i];
        sz[i]=n;
        dfs(i,g,sz,a,b,c,st);
        sz[i]=o;
        sz[st]=n;
    }
}

void dfs_sz(int st, vector<int>g[], int sz[], int p){
    sz[st]=1;
    for(int i : g[st]){
        if(i==p)
            continue;
        dfs_sz(i,g,sz,st);
        sz[st]+=sz[i];
    }
}

vector<int>order;

void dfso(int st, vector<int>g[], bool vis[]){
    order.push_back(st);
    vis[st]=1;
    for(int i : g[st]){
        if(vis[i])
            continue;
        dfso(i,g,vis);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    vector<int>ans(n,0);
    vector<int>g[n];
    int m = p.size();
    for(int i = 0;i<m;i++){
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    assert(m==n-1);
    rt=-1;
    int sz[n];
    dfs_sz(0,g,sz,-1);
    dfs(0,g,sz,a,b,c,-1);
    if(rt==-1){
        return ans;
    }
    dfs_sz(rt,g,sz,-1);
    //sz reset according to rt
    for(int i : g[rt]){
        int st = rt;
        if(sz[i]>=a&&sz[st]-sz[i]>=min(b,c)){
            //must set all to a
            bool vis[n];
            fill(vis,vis+n,0);
            vis[rt]=1;
            order.clear();
            dfso(i,g,vis);
            //order has all elements now
            //must set a of them to 1
            for(int i = 0;i<a;i++){
                ans[order[i]]=1;
            }
            //now must set other parts to val according to min (b,c)
            order.clear();
            vis[rt]=0;
            dfso(rt,g,vis);
            if(b<c){
                for(int i = 0;i<b;i++){
                    ans[order[i]]=2;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=3;
                    }
                }
            }
            else{
                for(int i = 0;i<c;i++){
                    ans[order[i]]=3;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=2;
                    }
                }
            }
            return ans;
        }
        if(sz[i]>=b&&sz[st]-sz[i]>=min(a,c)){
            //must set all to b
            bool vis[n];
            fill(vis,vis+n,0);
            vis[rt]=1;
            order.clear();
            dfso(i,g,vis);
            //order has all elements now
            //must set a of them to 1
            for(int i = 0;i<b;i++){
                ans[order[i]]=2;
            }
            //now must set other parts to val according to min (b,c)
            order.clear();
            vis[rt]=0;
            dfso(rt,g,vis);
            if(a<c){
                for(int i = 0;i<a;i++){
                    ans[order[i]]=1;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=3;
                    }
                }
            }
            else{
                for(int i = 0;i<c;i++){
                    ans[order[i]]=3;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=1;
                    }
                }
            }
            return ans;
        }
        if(sz[i]>=c&&sz[st]-sz[i]>=min(b,a)){

            //must set all to c
            bool vis[n];
            fill(vis,vis+n,0);
            vis[rt]=1;
            order.clear();
            dfso(i,g,vis);
            //order has all elements now
            //must set a of them to 1
            for(int i = 0;i<c;i++){
                ans[order[i]]=3;
            }
            //now must set other parts to val according to min (b,c)
            order.clear();
            vis[rt]=0;
            dfso(rt,g,vis);
            if(b<a){
                for(int i = 0;i<b;i++){
                    ans[order[i]]=2;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=1;
                    }
                }
            }
            else{
                for(int i = 0;i<a;i++){
                    ans[order[i]]=1;
                }
                for(int i = 0;i<n;i++){
                    if(ans[i]==0){
                        ans[i]=2;
                    }
                }
            }
            return ans;
        }
    }
    return ans;
}

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