oj.uz

Submission #295122

# Submission time Handle Problem Language Result Execution time Memory
295122 2020-09-09T13:36:01 Z SamAnd Split the Attractions (IOI19_split) C++17
22 / 100
 662 ms 1048580 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;

int n, m;
vector<int> g[N];

int q[N];
int p0[N];
void dfs0(int x, int p)
{
    p0[x] = p;
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }
}

pair<int, int> u[4];

vector<int> ans;

void dfs(int x, int p, int y)
{
    if (!u[y].fi)
        return;
    ans[x - 1] = u[y].se;
    --u[y].fi;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs(h, x, y);
    }
}

vector<int> find_split(int N_, int A, int B, int C, vector<int> P, vector<int> Q)
{
    n = N_;
    m = sz(P);
    for (int i = 0; i < m; ++i)
    {
        int x = P[i];
        int y = Q[i];
        ++x;
        ++y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    u[1] = m_p(A, 1);
    u[2] = m_p(B, 2);
    u[3] = m_p(C, 3);
    sort(u + 1, u + 3 + 1);

    dfs0(1, 1);
    for (int x = 1; x <= n; ++x)
    {
        if (u[1].fi <= min(q[x], n - q[x]) && u[2].fi <= max(q[x], n - q[x]))
        {
            ans.assign(n, 0);
            if (q[x] < n - q[x])
            {
                dfs(x, p0[x], 1);
                dfs(p0[x], x, 2);
            }
            else
            {
                dfs(x, p0[x], 2);
                dfs(p0[x], x, 1);
            }
            for (int i = 0; i < n; ++i)
            {
                if (!ans[i])
                    ans[i] = u[3].se;
            }
            return ans;
        }
    }
    ans.assign(n, 0);
    return ans;
}

Compilation message

split.cpp: In function 'void dfs0(int, int)':
split.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Runtime error 662 ms 1048576 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 628 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 98 ms 11384 KB ok, correct split
3 Correct 31 ms 7652 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 128 ms 14456 KB ok, correct split
6 Correct 117 ms 14328 KB ok, correct split
7 Correct 114 ms 14200 KB ok, correct split
8 Correct 121 ms 15228 KB ok, correct split
9 Correct 116 ms 14072 KB ok, correct split
10 Correct 29 ms 7552 KB ok, no valid answer
11 Correct 42 ms 8824 KB ok, no valid answer
12 Correct 80 ms 12664 KB ok, no valid answer
13 Correct 106 ms 12536 KB ok, no valid answer
14 Correct 69 ms 12784 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 653 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 662 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -