oj.uz

Submission #281696

# Submission time Handle Problem Language Result Execution time Memory
281696 2020-08-23T10:02:40 Z hoanghq2004 Split the Attractions (IOI19_split) C++14
22 / 100
 643 ms 1048580 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;
const int N = 100005;

int n;
pair <int, int> a, b, c;
vector <int> C, adj[N], E[N];
int sz[N], check[N];

void dfs(int u, int p)
{
    sz[u] = 1;
    check[u] = 1;
    for (auto v: adj[u])
    {
        if (v == p) continue;
        E[u].push_back(v);
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] >= a.first) check[u] = 0;
    }
    if (sz[u] < a.first || n - sz[u] < a.first) check[u] = 0;
}


void color(int u, int num, int cl)
{
    queue <int> q;
    q.push(u);
    C[u] = cl;
    int cnt = 1;
    if (cnt == num) return;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v: E[u])
            if (!C[v])
            {
                ++cnt;
                C[v] = cl;
                q.push(v);
                if (num == cnt) return;
            }
    }
}


vector <int> find_split(int _n, int _a, int _b, int _c, vector <int> u, vector <int> v)
{
    n = _n;
    a = {_a, 1}, b = {_b, 2}, c = {_c, 3};

    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);

    assert(a <= b && b <= c);

    int m = (int)v.size();
    C = vector <int> (n, 0);

    for (int i = 0; i < m; i ++)
    {
        adj[v[i]].push_back(u[i]);
        adj[u[i]].push_back(v[i]);
    }
    dfs(0, 0);
    for (int u = 1; u < n; ++u)
        if (check[u])
        {
            if (sz[u] <= n - sz[u])
            {
                color(u, a.first, a.second);
                color(0, b.first, b.second);
            }
            else
            {
                color(u, b.first, b.second);
                color(0, a.first, a.second);
            }
            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
    return C;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Runtime error 620 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Runtime error 607 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Correct 99 ms 14200 KB ok, correct split
3 Correct 34 ms 8704 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 110 ms 18712 KB ok, correct split
6 Correct 117 ms 18424 KB ok, correct split
7 Correct 114 ms 18168 KB ok, correct split
8 Correct 107 ms 19832 KB ok, correct split
9 Correct 113 ms 18140 KB ok, correct split
10 Correct 28 ms 8064 KB ok, no valid answer
11 Correct 41 ms 9548 KB ok, no valid answer
12 Correct 76 ms 13556 KB ok, no valid answer
13 Correct 91 ms 14028 KB ok, no valid answer
14 Correct 63 ms 13296 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 643 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Runtime error 620 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -