oj.uz

Submission #143789

# Submission time Handle Problem Language Result Execution time Memory
143789 2019-08-15T05:51:41 Z jwvg0425 Split the Attractions (IOI19_split) C++17
33 / 100
 159 ms 12840 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);
    }
}

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);

        queue<int> que;
        que.push(1);
        b--;
        num[1] = 2;

        while (!que.empty() && b > 0)
        {
            auto now = que.front();
            que.pop();

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

                if (b == 0)
                    break;

                num[e] = 2;
                que.push(e);
                b--;
            }
        }

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

        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:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
split.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (p.size() == n - 1)
         ~~~~~~~~~^~~~~~~~

Subtask #1
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 Incorrect 4 ms 3064 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

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 4 ms 3064 KB ok, correct split
4 Correct 95 ms 9352 KB ok, correct split
5 Correct 152 ms 8976 KB ok, correct split
6 Correct 71 ms 8184 KB ok, correct split
7 Correct 110 ms 12840 KB ok, correct split
8 Correct 159 ms 10616 KB ok, correct split
9 Correct 78 ms 8156 KB ok, correct split
10 Correct 63 ms 9328 KB ok, correct split
11 Correct 65 ms 9524 KB ok, correct split
12 Correct 69 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 82 ms 9080 KB ok, correct split
3 Correct 33 ms 5496 KB ok, correct split
4 Correct 4 ms 3064 KB ok, correct split
5 Correct 107 ms 11056 KB ok, correct split
6 Correct 98 ms 10744 KB ok, correct split
7 Correct 98 ms 10744 KB ok, correct split
8 Correct 93 ms 11900 KB ok, correct split
9 Correct 100 ms 10616 KB ok, correct split
10 Correct 28 ms 4984 KB ok, no valid answer
11 Correct 37 ms 5880 KB ok, no valid answer
12 Correct 68 ms 8820 KB ok, no valid answer
13 Correct 79 ms 8696 KB ok, no valid answer
14 Correct 63 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3064 KB invalid split: #1=1, #2=2, #3=6
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 Incorrect 4 ms 3064 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -