Submission #816987

#	Time	Username	Problem	Language	Result	Execution time	Memory
816987		vjudge1	Split the Attractions (IOI19_split)	C++17	100 / 100	139 ms	30000 KiB

split

#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
vi G[100100], children[100100];
bool vis[100100];
int A, B, C, N, timer = 0, tez[100100], tag[100100], low[100100];
vi ret;
bool found = false, special[100100];

void dfs2(int at, int tip, int &cnt){
    if(cnt > 0){
        cnt--;
        ret[at] = tip;
    }
    else{
        ret[at] = 3;
    }
 
    for(auto next:children[at]){
        dfs2(next, tip,cnt);
    }
}
void dfs3(int at,int tip,int &cnt){
    if(cnt > 0){
        cnt--;
        ret[at] = tip;
    }
    else{
        ret[at] = 3;
    }
 
    for(auto next:G[at]){
        if(ret[next] == 0){
            dfs3(next,tip,cnt);
        }
    }
}
void dfs(int at){
	tag[at] = low[at] = ++timer;
    tez[at] = 1;
    for(auto next:G[at]){
        if(tag[next] == 0){
            dfs(next);
            children[at].pb(next);
            tez[at] += tez[next];
            low[at] = min(low[at],low[next]);
        }
        else{
            low[at] = min(low[at],tag[next]);
        }
    }
    if(found){
        return ;
    }
    if(tez[at] >= A){
        int tmp = tez[at];
 
        for(auto next:children[at]){
            if(low[next] < tag[at] && tmp - tez[next] >= A){
                tmp -= tez[next];
                special[next] = true;
            }
        }
 
        if(tmp >= A && N- tmp >= B){
            found = true;
            int need  = A-1;
            ret[at] = 1;
            for(auto next:children[at]){
                if(special[next] == true){
                    continue;
                }
                dfs2(next,1,need );
            }
            need = B;
            dfs3(0,2,need);
 
        }
        else if(tmp >= B && N - tmp >= A){
            found = true;
            int need = B - 1;
            ret[at] = 2;
            for(auto next:children[at]){
                if(special[next] == true){
                    continue;
                }
                dfs2(next,2,need);
            }
            need= A;
            dfs3(0,1,need);
        }
	}
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
	vi put = {0, 1, 2, 3};
	if(b < a){
		swap(a, b);
		swap(put[1], put[2]);
	}
	else if(c < a){
		swap(a, c);
		swap(put[1], put[3]);
	}
	if(b > c){
		swap(b, c);
		swap(put[2], put[3]);
	}
	A = a; B = b; C = c; N = n;
	ret.resize(n,0);
	for(int i = 0; i < (int)q.size(); i++){
		G[p[i]].pb(q[i]);
		G[q[i]].pb(p[i]);
	}
	dfs(0);
	for(int i = 0; i < n; i++){
		ret[i] = put[ret[i]];
	}
	return ret;
}

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