Submission #1107082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107082		snpmrnhlol	Split the Attractions (IOI19_split)	C++17	100 / 100	69 ms	19540 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int inf = 1e9;
pair<int,int> v[3];
vector <int> e[N];
int dpth[N], low[N], vis[N], pr[N], sub[N];
vector <int> res;
vector <int> c;
bool add[N];
int n;
void dfs(int node, int p, int d){
    dpth[node] = d;
    low[node] = d;
    vis[node] = 1;
    pr[node] = p;
    sub[node] = 1;
    for(auto i:e[node]){
        if(i == p)continue;
        if(!vis[i]){
            dfs(i, node, d + 1);
            sub[node]+=sub[i];
            low[node] = min(low[node], low[i]);
        }else{
            low[node] = min(low[node], dpth[i]);
        }
    }
}
int cnt = 0;
void assignsubtree(int node, int id){
    if(cnt != 0){
        res[node] = id;cnt--;
    }
    for(auto i:e[node]){
        if(pr[i] == node){
            assignsubtree(i, id);
        }
    }
}
void dfs2(int node, int id){
    res[node] = id;cnt--;
    if(cnt == 0)return;
    for(auto i:e[node]){
        if(cnt != 0 && res[i] == 0){
            dfs2(i, id);
        }
        if(cnt == 0)return;
    }
}
bool checkok(int node, int sz1, int sz2){
    //cout<<"check:"<<node<<' '<<sz1<<' '<<sz2<<'\n';
    for(int j = 0;j < 2;j++){
        if(sz1 >= v[j].first && sz2 >= v[j^1].first){
            res[node] = v[j].second;
            cnt = v[j].first - 1;
            for(auto i:e[node]){
                if(pr[i] == node && add[i]){
                    assignsubtree(i, v[j].second);
                }
            }
            cnt = v[j^1].first;
            dfs2(pr[node], v[j^1].second);
            return 1;
        }
    }
    return 0;
}
bool check(int node){
    for(auto i:e[node]){
        if(pr[i] == node){
            add[i] = 1;
        }
    }
    int sz1 = sub[node], sz2 = n - sub[node];
    if(checkok(node, sz1, sz2)){
        return 1;
    }
    for(auto i:e[node]){
        if(pr[i] == node && low[i] < dpth[node]){
            sz1-=sub[i];
            sz2+=sub[i];
            add[i] = 0;
            if(checkok(node, sz1, sz2)){
                return 1;
            }
        }
    }
    return 0;
}
vector<int> find_split(int n2, int a, int b, int c, vector<int> p, vector<int> q) {
	n = n2;
	res.resize(n);
	for(int i = 0;i < (int)p.size();i++){
        e[p[i]].push_back(q[i]);
        e[q[i]].push_back(p[i]);
	}
	v[0] = {a, 1};
	v[1] = {b, 2};
    v[2] = {c, 3};
    sort(v, v + 3);
    dfs(0, -1, 0);
    bool ans = 0;
    for(int i = 0;i < n;i++){
        if(check(i)){
            ans = 1;
            break;
        }
    }
    if(ans){
        for(int i = 0;i < n;i++){
            if(res[i] == 0)res[i] = v[2].second;
        }
    }
	return res;
}
/**
9, 4, 2, 3, [0, 0, 0, 0, 0, 0, 1, 3, 4, 5],
[1, 2, 3, 4, 6, 8, 7, 7, 5, 6]

9 10 4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
**/

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