제출 #893482

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

split

#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

const int N = 1e5 + 10;

int n, m, sz[3], tmp[3], subsz[N], h[N], mnh[N], A, B, par[N], which[N];
bool vis[N], done, impossible;
vector<int> g[N], ans;

void color(int v, int col){
    // cout << "coloring " << v << " with color = " << col << ", remaining of this color are " << tmp[col - 1] << " and ans[v] = " << ans[v] << endl; 
    if (tmp[col - 1] == 0) return;
    if (ans[v]) return;

    tmp[col - 1]--;
    ans[v] = col;

    for (int u : g[v])
        if (h[u] == h[v] + 1)
            color(u, col);
}

void color_all(int v, int col){
    if (tmp[col - 1] == 0) return;
    if (ans[v]) return;

    tmp[col - 1]--;
    ans[v] = col;

    for (int u : g[v])
        color_all(u, col);
}

void pre_dfs(int v, int p = -1){
    vis[v] = 1;
    mnh[v] = h[v];
    subsz[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;
        
        if (vis[u]){ // back edge
            if (mnh[v] > h[u])
                which[v] = v;
            mnh[v] = min(mnh[v], h[u]);
            continue;
        }

        // child of u.
        h[u] = h[v] + 1;
        par[u] = v;
        pre_dfs(u, v);
        mnh[v] = min(mnh[v], mnh[u]);

        subsz[v] += subsz[u];
    }
}

void dfs(int v, int p = -1){
    vis[v] = 1;
    
    bool bad = 0;
    for (int u : g[v]){
        if (u == p) continue;
        
        if (vis[u])
            continue;

        // child of u.
        dfs(u, v);
        if (done) return;

        bad |= (subsz[u] >= sz[0]);
    }

    bad |= (subsz[v] < sz[0]);
    if (bad) return;
    
    // subsz[v] >= a and subsz[child(v)] < a.
    int forced = 1; // v is itself forced.
    vector<int> free, not_free;
    for (int u : g[v]){
        if (h[u] != h[v] + 1) continue;
        if (mnh[u] >= h[v]){
            forced += subsz[u];
            not_free.push_back(u);
        }
        else free.push_back(u);
    }

    while (forced < sz[0]){
        int u = free.back();
        free.pop_back();

        forced += subsz[u];
        not_free.push_back(u);
    }

    // cout << "AT v = " << v << endl;

    if (n - forced >= sz[1]){
        ans[v] = A;
        tmp[A - 1]--;
        for (int u : not_free)
            color(u, A);

        color_all(0, B);
    }
    else if (n - forced >= sz[0]){
        ans[v] = B;
        tmp[B - 1]--;
        for(int u : not_free)
            color(u, B);

        color_all(0, A);
    }
    else
        impossible = 1;

    done = 1;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){
    tmp[0] = a, tmp[1] = b, tmp[2] = c;
    sz[0] = a, sz[1] = b, sz[2] = c;
    sort(sz, sz + 3);

    if (sz[0] == a and sz[1] == b){
        A = 1;
        B = 2;
    }
    else if (sz[0] == a and sz[1] == c){
        A = 1;
        B = 3;
    }
    else if (sz[0] == b and sz[1] == a){
        A = 2;
        B = 1;
    }
    else if (sz[0] == b and sz[1] == c){
        A = 2;
        B = 3;
    }
    else if (sz[0] == c and sz[1] == a){
        A = 3;
        B = 1;
    }
    else{
        A = 3;
        B = 2;
    }

    // cout << A << " -- " << B << endl;

    n = N;
    m = p.size();

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

    ans.resize(n, 0);

    pre_dfs(0);
    memset(vis, 0, sizeof vis);
    dfs(0);

    if (impossible) return ans;
    for (int v = 0; v < n; v ++)
        if (!ans[v]) ans[v] = 6 - (A + B);

    return ans;
}

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