Submission #893431

#	Time	Username	Problem	Language	Result	Execution time	Memory
893431		Ghulam_Junaid	Split the Attractions (IOI19_split)	C++17	7 / 100	62 ms	22368 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];
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 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
            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;
    for (int u : g[v]){
        if (h[u] != h[v] + 1) continue;
        if (mnh[u] >= h[v])
            forced += subsz[u];
        else free.push_back(u);
    }

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

        forced += subsz[u];
    }

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

    if (n - forced >= sz[1]){
        int cur = v;
        while (cur != 0 && tmp[B - 1] > 0){
            cur = par[cur];
            ans[cur] = B;
            tmp[B - 1]--;
        }

        for (int u : free)
            color(u, B);
        
        color(v, A);
        for (int u : g[0])
            color(u, B);
    }
    else if (n - forced >= sz[0]){
        int cur = v;
        while (cur != 0 && tmp[A - 1] > 0){
            cur = par[cur];
            ans[cur] = A;
            tmp[A - 1]--;
        }
        for (int u : free)
            color(u, A);
        color(v, B);
        for (int u : g[0])
            color(u, 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: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36