Submission #1048931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048931		aykhn	Split the Attractions (IOI19_split)	C++17	22 / 100	498 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MXN = 1e5 + 5;
 
int n;
vector<int> ans;
vector<int> adj[MXN];
array<int, 2> col[3];
int sz[MXN], par[MXN], r;
int used[MXN], cnt;
 
void dfs(int a, int p)
{
    par[a] = p;
    sz[a] = 1;
    for (int &v : adj[a])
    {
        if (v == p) continue;
        dfs(v, a);
        sz[a] += sz[v];
    }
    if (sz[a] >= col[0][0] && n - sz[a] >= col[1][0]) r = a;
    else if (sz[a] >= col[1][0] && n - sz[a] >= col[0][0]) r = a;
}
void dfs1(int a, int c)
{
    if (cnt >= col[c][0]) return;
    used[a] = 1;
    ans[a] = col[c][1];
    cnt++;
    for (int &v : adj[a])
    {
        if (used[v]) continue;
        dfs1(v, c);
    }
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
    n = N;
    ans.assign(n, 0);
    r = -1;
    // for (int i = 1; i <= n; i++) adj[i].clear();
    col[0] = {a, 1}, col[1] = {b, 2}, col[2] = {c, 3};
    sort(col, col + 3);
    for (int i = 0; i < p.size(); i++)
    {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    dfs(0, 0);
    if (r == -1) return ans;
    fill(used, used + n, 0);
    used[par[r]] = 1;
    dfs1(r, (sz[r] <= n - sz[r]) ^ 1);
    cnt = 0;
    used[par[r]] = 0;
    dfs1(par[r], (sz[r] <= n - sz[r]));
    for (int &i : ans) if (i == 0) i = col[2][1];
	return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36