Submission #415592

#	Time	Username	Problem	Language	Result	Execution time	Memory
415592		xyz	Split the Attractions (IOI19_split)	C++17	0 / 100	590 ms	1048580 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
typedef long long ll;


const int N = 1e5 + 10;
vector<int> g[N];
int A[3], B[3], sub[N], n, Max[4], have[4], par[N];
vector<int> result, bad;

void dfs1(int v, int p){
    par[v] = p;
    sub[v] = 1;
    for(int x : g[v]){
        if(x != p){
            dfs1(x, v);
            sub[v] += sub[x];
        }
    }
}

int dfs2(int v, int p){
    if(sub[v] >= A[0] && n - sub[v] >= A[1])
        return v;
    for(int x : g[v]){
        if(x == p)
            continue;
        int u = dfs2(x, v);
        if(u != -1)
            return u;
    }
    return -1;
}

void paint(int v){
    result[v] = B[0];
    for(int x : g[v])
        if(x != par[v])
            paint(x);
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size();
    n = N;
    for(int i = 0; i < m; i ++){
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    A[0] = a, B[0] = 1, Max[1] = a;
    A[1] = b, B[1] = 2, Max[2] = b;
    A[2] = c, B[2] = 3, Max[3] = c;
    if(A[2] < A[1]){
        swap(A[2], A[1]);
        swap(B[2], B[1]);
    }
    if(A[2] < A[0]){
        swap(A[2], A[0]);
        swap(B[2], B[0]);
    }
//    for(int i = 0; i < 3; i ++)
//        cout << A[i] << " " << B[i] << endl;
//    for(int i = 1; i <= 3; i ++)
//        cout << i << " : " << Max[i] << endl;
    result.resize(n);
    bad.resize(n);
    if(m == n - 1){
        dfs1(0, -1);
        int k = dfs2(0, 0);
        if(k == -1)
            return bad;
//        cout << k << endl;
        for(int i = 0; i < n; i ++)
            result[i] = B[1];
        paint(k);
        for(int i = 0; i < n; i ++){
            int x = B[2];
            if(result[i] != 0 && have[result[i]] + 1 <= Max[result[i]])
                x = result[i];
            result[i] = x;
            have[x] ++;
        }
        assert(have[1] == Max[1]);
        assert(have[2] == Max[2]);
        assert(have[3] == Max[3]);
        return result;
    }
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

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