Submission #219753

#	Time	Username	Problem	Language	Result	Execution time	Memory
219753		VEGAnn	Split the Attractions (IOI19_split)	C++14	18 / 100	120 ms	14196 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 100100;
vector<int> g[N], vc;
bool mrk[N];

void dfs(int v){
    if (mrk[v]) return;
    mrk[v] = 1;
    vc.PB(v);

    for (int u : g[v])
        dfs(u);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res;
	res.resize(n);
	fill(all(res), 0);

	for (int i = 0; i < sz(p); i++){
        g[p[i]].PB(q[i]);
        g[q[i]].PB(p[i]);
	}

	bool was = 0;

	for (int i = 0; i < n; i++)
        if (sz(g[i]) == 1){
            was = 1;
            dfs(i);
            break;
        }

    if (!was) dfs(0);

	for (int i = 0; i < a; i++)
        res[vc[i]] = 1;

	for (int i = 0; i < b; i++)
        res[vc[a + i]] = 2;

	for (int i = 0; i < c; i++)
        res[vc[a + b + i]] = 3;

	return res;
}

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