Submission #343864

#	Time	Username	Problem	Language	Result	Execution time	Memory
343864		79brue	Split the Attractions (IOI19_split)	C++14	22 / 100	107 ms	12524 KiB

split

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

using namespace std;

typedef long long ll;

int n, m, a, b, c;
vector<int> link[100002];
int idx[4];
vector<int> ret;
int cnt;
int DP[100002];
int tmp=-1;

int dfs(int x, int p = -1){
    DP[x] = 1;
    for(auto y: link[x]){
        if(p==y) continue;
        DP[x] += dfs(y, x);
    }
    if(min(DP[x], n - DP[x]) >= a && max(DP[x], n - DP[x]) >= b){
        tmp = x;
    }
    return DP[x];
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
    m = (int)p.size();
    n = _n, a = _a, b = _b, c = _c;
    if(m != n-1) exit(1);

    vector<pair<int, int> > v {make_pair(a, 1), make_pair(b, 2), make_pair(c, 3)};
    sort(v.begin(), v.end());
    a = v[0].first, b = v[1].first, c = v[2].first;
    idx[1] = v[0].second, idx[2] = v[1].second, idx[3] = v[2].second;

    for(int i=0; i<m; i++){
        link[p[i]].push_back(q[i]);
        link[q[i]].push_back(p[i]);
    }
    ret.resize(n);

    dfs(0);
    if(tmp == -1) return ret;

    int rootNum, childNum;
    if(DP[tmp] >= a && n-DP[tmp] >= b) rootNum = 2, childNum = 1;
    else rootNum = 1, childNum = 2;

    queue<int> tq; tq.push(0);
    for(int cnt=0; cnt<((DP[tmp] >= a && n-DP[tmp] >= b) ? b : a); cnt++){\
        int tmp2 = tq.front(); tq.pop();
        ret[tmp2] = rootNum;
        for(auto y: link[tmp2]){
            if(y == tmp || ret[y]) continue;
            tq.push(y);
        }
    }
    while(!tq.empty()) tq.pop();
    tq.push(tmp);
    for(int cnt=0; cnt<((DP[tmp] >= a && n-DP[tmp] >= b) ? a : b); cnt++){
        if(tq.empty()) return ret;
        int tmp2 = tq.front(); tq.pop();
        ret[tmp2] = childNum;
        for(auto y: link[tmp2]){
            if(ret[y]) continue;
            tq.push(y);
        }
    }
    for(int i=0; i<n; i++) if(!ret[i]) ret[i] = 3;
    for(int i=0; i<n; i++) ret[i] = idx[ret[i]];
    return ret;
}

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