oj.uz

Submission #143790

# Submission time Handle Problem Language Result Execution time Memory
143790 2019-08-15T05:57:33 Z jwvg0425 Split the Attractions (IOI19_split) C++17
40 / 100
 159 ms 14912 KB 
#include "split.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> edge[100005];
int sub[100005];
int parent[100005];
int check[100005];

void dfs(int root)
{
    sub[root] = 1;
    for (auto&e : edge[root])
    {
        if (e == parent[root])
            continue;

        parent[e] = root;
        dfs(e);
        sub[root] += sub[e];
    }
}

void mark(int root, vector<int>& num, int& a, int& b)
{
    for (auto& e : edge[root])
    {
        if (e == parent[root])
            continue;

        if (check[e] == 0)
            check[e] = check[root];
    }

    if (check[root] == 1 && a > 0)
    {
        num[root] = 1;
        a--;
    }

    if (check[root] == 2 && b > 0)
    {
        num[root] = 2;
        b--;
    }

    for (auto& e : edge[root])
    {
        if (e == parent[root])
            continue;

        mark(e, num, a, b);
    }
}

void solve(vector<int>& num, int now, int k, int& count)
{
    if (count == 0)
        return;

    num[now] = k;
    count--;

    for (auto& e : edge[now])
    {
        if (num[e] != -1)
            continue;

        solve(num, e, k, count);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    memset(parent, -1, sizeof(parent));
    for (int i = 0; i < p.size(); i++)
    {
        edge[p[i]].push_back(q[i]);
        edge[q[i]].push_back(p[i]);
    }

    if (p.size() == n - 1)
    {
        vector<int> num(n, 0);

        dfs(0);

        for (int i = 1; i < n; i++)
        {
            int ai = sub[i];
            int bi = n - sub[i];

            if (min(ai, bi) < min(a, b) || max(ai, bi) < max(a, b))
                continue;

            if (ai >= a && bi >= b)
            {
                check[i] = 1;
                check[0] = 2;
            }
            else
            {
                check[0] = 1;
                check[i] = 2;
            }

            mark(0, num, a, b);

            for (int j = 0; j < n; j++)
            {
                if (num[j] == 0)
                    num[j] = 3;
            }

            break;
        }

        return num;
    }
    else
    {
        vector<int> num(n, -1);
        solve(num, 0, 1, a);

        for (int i = 0; i < n; i++)
        {
            if (num[i] != -1)
                continue;

            int deg = 0;

            for (auto& e : edge[i])
            {
                if (num[e] == -1)
                    deg++;
            }

            if (deg == 2)
                continue;

            solve(num, i, 2, b);
        }

        for (int i = 0; i < n; i++)
        {
            if (num[i] == -1)
                num[i] = 3;
        }

        return num;
    }
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
split.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (p.size() == n - 1)
         ~~~~~~~~~^~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Correct 4 ms 3064 KB ok, correct split
3 Correct 4 ms 3064 KB ok, correct split
4 Correct 4 ms 3064 KB ok, correct split
5 Correct 4 ms 3064 KB ok, correct split
6 Correct 5 ms 3064 KB ok, correct split
7 Correct 148 ms 14912 KB ok, correct split
8 Correct 110 ms 13048 KB ok, correct split
9 Correct 114 ms 12508 KB ok, correct split
10 Correct 77 ms 8184 KB ok, correct split
11 Correct 84 ms 9720 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Correct 5 ms 3064 KB ok, correct split
3 Correct 5 ms 3064 KB ok, correct split
4 Correct 102 ms 9420 KB ok, correct split
5 Correct 94 ms 9136 KB ok, correct split
6 Correct 80 ms 8184 KB ok, correct split
7 Correct 159 ms 13020 KB ok, correct split
8 Correct 128 ms 10488 KB ok, correct split
9 Correct 76 ms 8184 KB ok, correct split
10 Correct 64 ms 9328 KB ok, correct split
11 Correct 62 ms 9328 KB ok, correct split
12 Correct 85 ms 9328 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Correct 90 ms 9092 KB ok, correct split
3 Correct 33 ms 5496 KB ok, correct split
4 Correct 5 ms 3064 KB ok, correct split
5 Correct 100 ms 10968 KB ok, correct split
6 Correct 112 ms 10904 KB ok, correct split
7 Correct 110 ms 10744 KB ok, correct split
8 Correct 100 ms 11736 KB ok, correct split
9 Correct 99 ms 10652 KB ok, correct split
10 Correct 26 ms 4984 KB ok, no valid answer
11 Correct 38 ms 5880 KB ok, no valid answer
12 Correct 75 ms 8820 KB ok, no valid answer
13 Correct 82 ms 8700 KB ok, no valid answer
14 Correct 65 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3064 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Correct 4 ms 3064 KB ok, correct split
3 Correct 4 ms 3064 KB ok, correct split
4 Correct 4 ms 3064 KB ok, correct split
5 Correct 4 ms 3064 KB ok, correct split
6 Correct 5 ms 3064 KB ok, correct split
7 Correct 148 ms 14912 KB ok, correct split
8 Correct 110 ms 13048 KB ok, correct split
9 Correct 114 ms 12508 KB ok, correct split
10 Correct 77 ms 8184 KB ok, correct split
11 Correct 84 ms 9720 KB ok, correct split
12 Correct 4 ms 3064 KB ok, correct split
13 Correct 5 ms 3064 KB ok, correct split
14 Correct 5 ms 3064 KB ok, correct split
15 Correct 102 ms 9420 KB ok, correct split
16 Correct 94 ms 9136 KB ok, correct split
17 Correct 80 ms 8184 KB ok, correct split
18 Correct 159 ms 13020 KB ok, correct split
19 Correct 128 ms 10488 KB ok, correct split
20 Correct 76 ms 8184 KB ok, correct split
21 Correct 64 ms 9328 KB ok, correct split
22 Correct 62 ms 9328 KB ok, correct split
23 Correct 85 ms 9328 KB ok, correct split
24 Correct 4 ms 3064 KB ok, correct split
25 Correct 90 ms 9092 KB ok, correct split
26 Correct 33 ms 5496 KB ok, correct split
27 Correct 5 ms 3064 KB ok, correct split
28 Correct 100 ms 10968 KB ok, correct split
29 Correct 112 ms 10904 KB ok, correct split
30 Correct 110 ms 10744 KB ok, correct split
31 Correct 100 ms 11736 KB ok, correct split
32 Correct 99 ms 10652 KB ok, correct split
33 Correct 26 ms 4984 KB ok, no valid answer
34 Correct 38 ms 5880 KB ok, no valid answer
35 Correct 75 ms 8820 KB ok, no valid answer
36 Correct 82 ms 8700 KB ok, no valid answer
37 Correct 65 ms 8944 KB ok, no valid answer
38 Incorrect 4 ms 3064 KB 2 components are not connected
39 Halted 0 ms 0 KB -