Submission #617900

#	Time	Username	Problem	Language	Result	Execution time	Memory
617900		Jarif_Rahman	Split the Attractions (IOI19_split)	C++17	0 / 100	460 ms	1048576 KiB

split

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<int> s, so;
vector<vector<int>> v;
vector<int> sz;

vector<int> ans;

void pre_dfs(int nd, int ss = -1){
    for(int x: v[nd]) if(x != ss) pre_dfs(x, nd), sz[nd]+=sz[x];
}

int cnt;
void create_ans(int nd, int ss, int avoid, int id){
    if(cnt == 0) return;
    ans[nd] = id;
    cnt--;
    for(int x: v[nd]) if(x != ss && x != avoid && cnt) create_ans(x, nd, avoid, id);
}

void dfs(int nd, int ss = -1){
    if(ans.back()) return;
    if(sz[nd] >= s[0] && n-sz[nd] >= s[1]){
        fill(ans.begin(), ans.end(), so[2]+1);
        cnt = s[0];
        create_ans(nd, ss, -1, so[0]+1);
        cnt = s[1];
        create_ans(0, -1, nd, so[1]+1);
        return;
    }
    else if(sz[nd] >= s[1] && n-sz[nd] >= s[0]){
        fill(ans.begin(), ans.end(), so[2]+1);
        cnt = s[1];
        create_ans(nd, -1, -1, so[1]+1);
        cnt = s[0];
        create_ans(0, -1, nd, so[0]+1);
        return;
    }

    for(int x: v[nd]) if(x != ss && !ans.back()) dfs(x, nd);
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> P, vector<int> Q){
    n = _n;
    s = {_a, _b, _c};
    so = {0, 1, 2};
    sort(so.begin(), so.end(), [&](int a, int b){
        return s[a] < s[b];
    });
    sort(s.begin(), s.end());

    m = P.size();
    v.assign(n, {});
    sz.assign(n, 1);
    ans.assign(n, 0);

    for(int i = 0; i < m; i++) v[P[i]].pb(Q[i]), v[Q[i]].pb(P[i]);
    pre_dfs(0);
    dfs(0);

    return ans;
}

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