제출 #1283836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283836		duckindog	Split the Attractions (IOI19_split)	C++20	0 / 100	2 ms	344 KiB

split

#include <bits/stdc++.h>

#include "split.h"

using namespace std;

const int N = 100'000 + 10;
int n, a, b, c;
vector<int> ad[N];

vector<int> ret;

int sz[N];
void dfs0(int u, int p = -1) { 
    sz[u] = 1;
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        dfs0(v, u);
        sz[u] += sz[v];
    }
}

int k;
void dfs1(int u, int p, int color) { 
    if (k <= 0) return;
    k -= 1;
    
    ret[u] = color;
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        dfs1(v, u, color);
    }
}


bool doneColor = false;
void dfs2(int u, int p = -1) { 
    if (doneColor) return;

    bool isValid = true;
    for (const auto& v : ad[u]) {
        if (v == p) continue;
        dfs2(v, u);

        if (sz[v] >= a) isValid = false;
    }
    
    if (sz[u] < a || n - sz[u] < a) isValid = false;

    if (isValid && !doneColor && p != -1) { 
        
        // cerr << u << " " << sz[u] << " " << a << " " << b << " " << n - sz[u] << "\n";
        if (sz[u] >= b) { 
            doneColor = true;
            k = b;
            dfs1(u, p, 2);
            k = a;
            dfs1(p, u, 3);
        } else if (n - sz[u] >= b) {
            doneColor = true;
            k = b;
            dfs1(p, u, 2);
            k = a;
            dfs1(u, p, 3);

            // for (const auto& x : ret) cerr << x << " \n"[&x == &ret.back()];

        }
    }
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q) {
    { // input
        n = _n;
        a = _a;
        b = _b;
        c = _c;
        for (int i = 0; i < (int)_p.size(); ++i) { 
            int u = _p[i], v = _q[i];
            ad[u].push_back(v);
            ad[v].push_back(u);
        }

        if (a > b) swap(a, b);
        if (b > c) swap(b, c);
        if (a > b) swap(a, b);
    }
    assert((int)_p.size() == n - 1);
    ret.resize(n, 1);

    dfs0(0);
    dfs2(0);

    { // check
        int cntA = 0, cntB = 0, cntC = 0;
        for (const auto& x : ret) { 
            (x == 1 ? cntC : x == 2 ? cntB : cntA) += 1;
        }

        if (cntA != a || cntB != b || cntC != c) { 
            // cerr << "Wrong\n";
            // for (;;);
            ret.assign(n, 0);
        }


        // assert(cntA == a);
        // assert(cntB == b);
        // assert(cntC == c);
    }

    return ret;
}

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