oj.uz

Submission #295132

# Submission time Handle Problem Language Result Execution time Memory
295132 2020-09-09T13:40:38 Z SamAnd Split the Attractions (IOI19_split) C++17
33 / 100
 736 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 (ans[x - 1])
        return;
    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);

    if (u[1].fi == 1)
    {
        ans.assign(n, 0);
        dfs(1, 1, 2);
        for (int x = 0; x < n; ++x)
        {
            if (!ans[x])
            {
                ans[x] = u[1].se;
                break;
            }
        }
        for (int x = 0; x < n; ++x)
        {
            if (!ans[x])
                ans[x] = u[3].se;
        }
        return ans;
    }

    if (m != n - 1)
    {
        g[P.back()].pop_back();
        g[Q.back()].pop_back();
    }

    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:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     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 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 3 ms 4992 KB ok, correct split
6 Runtime error 736 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.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 135 ms 11640 KB ok, correct split
5 Correct 83 ms 10608 KB ok, correct split
6 Correct 87 ms 10488 KB ok, correct split
7 Correct 80 ms 12792 KB ok, correct split
8 Correct 130 ms 12844 KB ok, correct split
9 Correct 101 ms 10592 KB ok, correct split
10 Correct 76 ms 10864 KB ok, correct split
11 Correct 135 ms 10864 KB ok, correct split
12 Correct 67 ms 10864 KB ok, correct split

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 32 ms 7552 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 126 ms 13404 KB ok, correct split
6 Correct 116 ms 13176 KB ok, correct split
7 Correct 113 ms 13048 KB ok, correct split
8 Correct 107 ms 14072 KB ok, correct split
9 Correct 115 ms 12904 KB ok, correct split
10 Correct 26 ms 7168 KB ok, no valid answer
11 Correct 47 ms 8228 KB ok, no valid answer
12 Correct 89 ms 11536 KB ok, no valid answer
13 Correct 87 ms 11384 KB ok, no valid answer
14 Correct 67 ms 11632 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 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 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 3 ms 4992 KB ok, correct split
6 Runtime error 736 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -