제출 #1283848

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

split

#include <bits/stdc++.h>

#include "split.h"

using namespace std;

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

vector<int> ret;

void doColor(int u, int p, int idx) { 
    if (c[idx].second <= 0) return;
    c[idx].second -= 1;
    
    ret[u] = c[idx].first;
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        doColor(v, u, idx);
    }
}


int sz[N];
bool doneColor = false;
void dfs(int u, int p = -1) { 
    if (doneColor) return;
    sz[u] = 1;

    for (const auto& v : ad[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        
        if (doneColor) return;
    }

    if (sz[u] >= c[0].second && n - sz[u] >= c[0].second) { 
        // cerr << u << "\n";
        if (sz[u] >= c[1].second) { 
            doneColor = true;
            doColor(u, p, 1);
            doColor(p, u, 0);
        } else if (n - sz[u] >= c[1].second) {
            doneColor = true;
            doColor(p, u, 1);
            doColor(u, p, 0);
        }
    }
    
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q) {
    { // input
        n = _n;
        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);
        }

        c[0] = {1, _a};
        c[1] = {2, _b};
        c[2] = {3, _c};
        sort(c, c + 3);
    }
    assert((int)_p.size() == n - 1);
    ret.resize(n, 0);

    dfs(0);

    if (!doneColor) return ret;
    for (auto& x : ret) if (!x) x = c[2].first;

    return ret;
}

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