제출 #408953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408953		Tc14	Split the Attractions (IOI19_split)	C++17	100 / 100	134 ms	24880 KiB

split

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int n, cnt;
bool found, sol;
pii x, y, z;
tuple<int, int, int> bottom, top;
ve<int> Num, Low, Size;
ve<bool> B;
ve<ve<int>> G, C;

void dfs(int u, int p) {

    cnt++;
    Num[u] = cnt;
    Low[u] = cnt;

    Size[u] = 1;
    bool valid = true;

    for (int v : G[u]) {
        if (Num[v] == 0) {
            dfs(v, u);
            Low[u] = min(Low[u], Low[v]);
            Size[u] += Size[v];
            if (Size[v] >= x.first) valid = false;
            C[u].push_back(v);
        }
        else if (v != p) Low[u] = min(Low[u], Num[v]);
    }

    if (Size[u] < x.first) valid = false;

    if (valid && !found) {
        found = true;

        int curr = Size[u];
        for (int v : C[u]) {
            if (Low[v] < Num[u]) {
                if (curr - Size[v] >= x.first) {
                    curr -= Size[v];
                    B[v] = true;
                }
            }
        }

        int opp = n - curr;
        if (opp >= y.first) {
            sol = true;
            top = {y.first, y.second, p};
            bottom = {x.first, x.second, u};
        }
        else if (opp >= x.first) {
            sol = true;
            top = {x.first, x.second, p};
            bottom = {y.first, y.second, u};
        }
    }

}

ve<int> find_split(int _n, int a, int b, int c, ve<int> p, ve<int> q) {

    int m;
    ve<int> Ans;
    queue<int> Q;

    n = _n;
    m = (int)p.size();
    Num = ve<int>(n);
    Low = ve<int>(n);
    Size = ve<int>(n);
    B = ve<bool>(n);
    G = ve<ve<int>>(n);
    C = ve<ve<int>>(n);

    for (int i = 0; i < m; i++) {
        G[p[i]].push_back(q[i]);
        G[q[i]].push_back(p[i]);
    }

    ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
    sort(A.begin(), A.end());
    x = A[0];
    y = A[1];
    z = A[2];

    cnt = 0;
    found = false;
    sol = false;
    dfs(0, -1);

    if (sol) {

        Ans = ve<int>(n, z.second);

        int sz, t, s;
        tie(sz, t, s) = bottom;

        sz--;
        Ans[s] = t;
        Q.push(s);

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int v : C[u]) {
                if (!B[v]) {
                    if (sz > 0) {
                        sz--;
                        Ans[v] = t;
                        Q.push(v);
                    }
                }
            }
        }

        tie(sz, t, s) = top;

        sz--;
        Ans[s] = t;
        Q.push(s);

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int v : G[u]) {
                if (Ans[v] == z.second) {
                    if (sz > 0) {
                        sz--;
                        Ans[v] = t;
                        Q.push(v);
                    }
                }
            }
        }

    }
    else Ans = ve<int>(n);

	return Ans;
}

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