oj.uz

Submission #281771

# Submission time Handle Problem Language Result Execution time Memory
281771 2020-08-23T12:57:19 Z hoanghq2004 Split the Attractions (IOI19_split) C++14
18 / 100
 170 ms 25208 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];
int times, low[N], num[N];

void dfs(int u, int p)
{
    num[u] = low[u] = ++times;
    sz[u] = 1;
    check[u] = 1;
    for (auto v: adj[u])
    {
        if (v == p) continue;
        if (!num[v])
        {
            E[u].push_back(v);
            dfs(v, u);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            if (sz[v] >= a.first) check[u] = 0;
        }
        else low[u] = min(low[u], num[v]);
    }
}


void paint(int u, int num, int cl)
{
    queue <int> q;
    q.push(u);
    int cnt = 0;
    if (!C[u])
    {
        C[u] = cl;
        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;
            }
            else q.push(v);
    }
}


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] && sz[u] >= a.first && n - sz[u] >= a.first)
        {
            if (sz[u] <= n - sz[u])
            {
                paint(u, a.first, a.second);
                paint(0, b.first, b.second);
            }
            else
            {
                paint(u, b.first, b.second);
                paint(0, a.first, a.second);
            }
            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
//        if (check[u] && n - sz[u] < a.first)
//        {
//            int cnt = 0;
//            for (auto v: E[u])
//                if (low[v] < num[u]) cnt += sz[v];
//            if (cnt + n - sz[u] < a.first) continue;
//
//            C[u] = b.second;
//            cnt = 1;
//            for (auto v: E[u])
//                if (low[v] >= num[u])
//                {
//                    paint(v, b.first - cnt, b.second);
//                    cnt += sz[v];
//                    if (sz[v] <= 0) break;
//                }
//            paint(0, a.first, a.first);
//            cnt = n - sz[u];
//            for (int i = 0; i < n; ++i)
//                if (!C[i] && low[i] < num[u])
//                {
//                    C[i] = a.second;
//                    ++cnt;
//                    if (cnt == a.first) break;
//                }
//            for (int i = 0; i < n; ++i)
//                if (!C[i]) C[i] = c.second;
//            return C;
//        }
    }
    return C;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 4 ms 4992 KB ok, correct split
6 Correct 4 ms 4992 KB ok, correct split
7 Correct 124 ms 24568 KB ok, correct split
8 Correct 121 ms 21880 KB ok, correct split
9 Correct 120 ms 20984 KB ok, correct split
10 Correct 118 ms 24952 KB ok, correct split
11 Correct 131 ms 25208 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB ok, correct split
2 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 149 ms 19960 KB ok, correct split
5 Correct 118 ms 14208 KB ok, correct split
6 Correct 126 ms 25080 KB ok, correct split
7 Correct 137 ms 21624 KB ok, correct split
8 Correct 170 ms 16888 KB ok, correct split
9 Correct 123 ms 15736 KB ok, correct split
10 Correct 72 ms 13552 KB ok, correct split
11 Correct 64 ms 13552 KB ok, correct split
12 Correct 68 ms 13552 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Incorrect 107 ms 14200 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Correct 3 ms 4992 KB ok, no valid answer
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 3 ms 4992 KB ok, correct split
5 Correct 4 ms 4992 KB ok, correct split
6 Correct 3 ms 4992 KB ok, correct split
7 Correct 4 ms 4992 KB ok, correct split
8 Correct 3 ms 4992 KB ok, correct split
9 Correct 7 ms 5504 KB ok, correct split
10 Correct 6 ms 5376 KB ok, correct split
11 Correct 4 ms 4992 KB ok, correct split
12 Correct 7 ms 5376 KB ok, correct split
13 Correct 3 ms 4992 KB ok, correct split
14 Correct 4 ms 4992 KB ok, correct split
15 Correct 4 ms 4992 KB ok, correct split
16 Correct 4 ms 4992 KB ok, correct split
17 Correct 4 ms 4992 KB ok, correct split
18 Correct 4 ms 4992 KB ok, correct split
19 Correct 4 ms 5120 KB ok, correct split
20 Correct 4 ms 5120 KB ok, correct split
21 Correct 5 ms 5376 KB ok, correct split
22 Incorrect 5 ms 5376 KB 2 components are not connected
23 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 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 4 ms 4992 KB ok, correct split
6 Correct 4 ms 4992 KB ok, correct split
7 Correct 124 ms 24568 KB ok, correct split
8 Correct 121 ms 21880 KB ok, correct split
9 Correct 120 ms 20984 KB ok, correct split
10 Correct 118 ms 24952 KB ok, correct split
11 Correct 131 ms 25208 KB ok, correct split
12 Correct 5 ms 4992 KB ok, correct split
13 Correct 4 ms 4992 KB ok, correct split
14 Correct 4 ms 4992 KB ok, correct split
15 Correct 149 ms 19960 KB ok, correct split
16 Correct 118 ms 14208 KB ok, correct split
17 Correct 126 ms 25080 KB ok, correct split
18 Correct 137 ms 21624 KB ok, correct split
19 Correct 170 ms 16888 KB ok, correct split
20 Correct 123 ms 15736 KB ok, correct split
21 Correct 72 ms 13552 KB ok, correct split
22 Correct 64 ms 13552 KB ok, correct split
23 Correct 68 ms 13552 KB ok, correct split
24 Correct 4 ms 4992 KB ok, correct split
25 Incorrect 107 ms 14200 KB 2 components are not connected
26 Halted 0 ms 0 KB -