oj.uz

Submission #220046

# Submission time Handle Problem Language Result Execution time Memory
220046 2020-04-06T21:07:35 Z VEGAnn Split the Attractions (IOI19_split) C++14
0 / 100
 13 ms 9984 KB 
#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 100100;
vector<int> res;
vector<int> g[N], vc, children[N];
bool mrk[N];
int A[3], C[3], mrk_col[N], h[N], mn_h[N], pr[N], siz[N], mem = 0;

void dfs(int v, int p){
    pr[v] = p;
    siz[v] = 1;
    mrk[v] = 1;
    mn_h[v] = h[v];

    for (int u : g[v]){
        if (mrk[u]) continue;
        children[v].PB(u);
        h[u] = h[v] + 1;

        dfs(u, v);

        mn_h[v] = min(mn_h[v], mn_h[u]);
        siz[v] += siz[u];
    }
}

void col(int v, int cl){
    mrk_col[v] = cl;

    for (int u : children[v])
        col(u, cl);
}

void DFS(int v, int cl, int rlc){
    if (mrk[v]) return;
    if (mem == 0) return;

    mem--;
    mrk[v] = 1;
    res[v] = rlc;

    for (int u : g[v])
        if (mrk_col[u] == cl)
            DFS(u, cl, rlc);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);
	fill(all(res), 0);

	for (int i = sz(p) - 1; i >= 0; i++){
        g[p[i]].PB(q[i]);
        g[q[i]].PB(p[i]);
	}

	A[0] = a; A[1] = b; A[2] = c;
	C[0] = 1; C[1] = 2; C[2] = 3;

	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}
	if (A[1] > A[2]) {
        swap(A[1], A[2]);
        swap(C[1], C[2]);
	}
	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}

    dfs(0, -1);

    for (int v = 0; v < n; v++){
        bool ok = bool(siz[v] >= A[0]);

        for (int u : children[v])
            ok &= bool(siz[u] < A[0]);

        if (!ok) continue;

        col(0, 1);
        col(v, 2);

        int real_siz = siz[v];

        for (int u : children[v])
            if (mn_h[u] < h[v] && real_siz - siz[u] >= A[0]){
                real_siz -= siz[u];
                col(u, 1);
            }

        for (int t1 = 0; t1 < 2; t1++){
            int t2 = 1 - t1;

            if (real_siz >= A[t1] && n - real_siz >= A[t2]){
                fill(mrk, mrk + n, 0);

                mem = A[t2];
                DFS(pr[v], 1, C[t2]);

                mem = A[t1];
                DFS(v, 2, C[t1]);

                for (int &cr : res)
                    if (cr == 0)
                        cr = C[2];

                return res;
            }
        }
    }

	return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -