oj.uz

Submission #143788

# Submission time Handle Problem Language Result Execution time Memory
143788 2019-08-15T05:48:04 Z jwvg0425 Split the Attractions (IOI19_split) C++17
22 / 100
 1068 ms 1048580 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]);
    }

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

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++)
                     ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 1026 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 1052 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3064 KB ok, correct split
2 Correct 93 ms 9040 KB ok, correct split
3 Correct 33 ms 5496 KB ok, correct split
4 Correct 4 ms 3064 KB ok, correct split
5 Correct 100 ms 11004 KB ok, correct split
6 Correct 104 ms 10744 KB ok, correct split
7 Correct 122 ms 10616 KB ok, correct split
8 Correct 106 ms 11768 KB ok, correct split
9 Correct 94 ms 10488 KB ok, correct split
10 Correct 19 ms 4856 KB ok, no valid answer
11 Correct 45 ms 5880 KB ok, no valid answer
12 Correct 72 ms 8952 KB ok, no valid answer
13 Correct 76 ms 8696 KB ok, no valid answer
14 Correct 63 ms 8908 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1068 ms 1048576 KB Execution killed with signal 9 (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 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 1026 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -