제출 #1077382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077382		Ignut	Split the Attractions (IOI19_split)	C++17	22 / 100	586 ms	1048576 KiB

split

// Ignut

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 123;
int n;
int a, b, c;
int colorA, colorB, colorC;

vector<int> g[MAXN];
int sz[MAXN];
int parent[MAXN];

int flag = -1;
int vert = -1;

int dfs0(int v, int par) {
    sz[v] = 1;
    parent[v] = par;
    for (int to : g[v])
        if (to != par)
            sz[v] += dfs0(to, v);
    return sz[v];
}

vector<int> res;

int lim;

void dfs(int v, int par, int col) {
    res[v] = col;
    lim --;
    if (lim == 0) return;
    for (int to : g[v]) {
        if (to == par || to == vert)
            continue;
        if (lim == 0) return;
        dfs(to, v, col);
        if (lim == 0) return;
    }
}

vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
    vector<pair<int, int>> col = {{A, 1}, {B, 2}, {C, 3}};
    sort(col.begin(), col.end());
    A = col[0].first, colorA = col[0].second;
    B = col[1].first, colorB = col[1].second;
    C = col[2].first, colorC = col[2].second;

    int M = P.size();
    for (int i = 0; i < M; i ++) {
        g[P[i]].push_back(Q[i]);
        g[Q[i]].push_back(P[i]);
    }
    dfs0(0, -1);
    for (int i = 0; i < N; i ++) {
        if (sz[i] >= A && N - sz[i] >= B) {
            vert = i; flag = 1; break;
        }
        if (sz[i] >= B && N - sz[i] >= A) {
            vert = i; flag = 2; break;
        }
    }
    res.assign(N, 0);
    if (vert == -1)
        return res;
    
    // cout << A << ' ' << B << ' ' << C << '\n';
    // cout << colorA << '_' << colorB << '_' << colorC << '\n';
    // cout << vert << ' ' << flag << '\n';
    
    for (int i = 0; i < N; i ++) res[i] = colorC;

    if (flag == 1) {
        lim = B; dfs(0, -1, colorB);
        lim = A; dfs(vert, parent[vert], colorA);
    }
    else {
        lim = A; dfs(0, -1, colorA);
        lim = B; dfs(vert, parent[vert], colorB);
    }

    return res;
}

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