oj.uz

Submission #893431

# Submission time Handle Problem Language Result Execution time Memory
893431 2023-12-27T04:49:30 Z Ghulam_Junaid Split the Attractions (IOI19_split) C++17
7 / 100
 62 ms 22368 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok, correct split
2 Correct 1 ms 2652 KB ok, correct split
3 Correct 1 ms 2652 KB ok, correct split
4 Correct 1 ms 2652 KB ok, correct split
5 Correct 1 ms 2908 KB ok, correct split
6 Correct 1 ms 2908 KB ok, correct split
7 Correct 57 ms 21708 KB ok, correct split
8 Correct 53 ms 15076 KB ok, correct split
9 Correct 62 ms 15496 KB ok, correct split
10 Correct 51 ms 22212 KB ok, correct split
11 Correct 54 ms 22196 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB ok, correct split
2 Correct 1 ms 2652 KB ok, correct split
3 Correct 1 ms 2652 KB ok, correct split
4 Correct 57 ms 14568 KB ok, correct split
5 Correct 41 ms 9812 KB ok, correct split
6 Correct 53 ms 22368 KB ok, correct split
7 Correct 47 ms 17752 KB ok, correct split
8 Incorrect 62 ms 12060 KB invalid split: #1=1, #2=25, #3=99974
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok, correct split
2 Incorrect 41 ms 9812 KB invalid split: #1=13, #2=40000, #3=59987
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB ok, correct split
2 Correct 1 ms 2652 KB ok, no valid answer
3 Correct 1 ms 2648 KB ok, correct split
4 Incorrect 1 ms 2652 KB invalid split: #1=2, #2=3, #3=6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok, correct split
2 Correct 1 ms 2652 KB ok, correct split
3 Correct 1 ms 2652 KB ok, correct split
4 Correct 1 ms 2652 KB ok, correct split
5 Correct 1 ms 2908 KB ok, correct split
6 Correct 1 ms 2908 KB ok, correct split
7 Correct 57 ms 21708 KB ok, correct split
8 Correct 53 ms 15076 KB ok, correct split
9 Correct 62 ms 15496 KB ok, correct split
10 Correct 51 ms 22212 KB ok, correct split
11 Correct 54 ms 22196 KB ok, correct split
12 Correct 1 ms 2648 KB ok, correct split
13 Correct 1 ms 2652 KB ok, correct split
14 Correct 1 ms 2652 KB ok, correct split
15 Correct 57 ms 14568 KB ok, correct split
16 Correct 41 ms 9812 KB ok, correct split
17 Correct 53 ms 22368 KB ok, correct split
18 Correct 47 ms 17752 KB ok, correct split
19 Incorrect 62 ms 12060 KB invalid split: #1=1, #2=25, #3=99974
20 Halted 0 ms 0 KB -