Submission #520992

#	Time	Username	Problem	Language	Result	Execution time	Memory
520992		lordlorinc	Split the Attractions (IOI19_split)	C++17	0 / 100	0 ms	204 KiB

split

#include "split.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> res;
vector<vector<int> > graph;
vector<bool> vis;

int dfs(int pos, int a, int b){
    // cout << pos << " " << a << " " << b << endl;
    bool ae = true;
    if (a != 0) {

        res[pos] = 1;
        a--;
    }
    else {
        ae = false;
        res[pos] = 2;
        b--;
    }

    vis[pos] = true;

    for (int x : graph[pos]){
        if(vis[x]) continue;
        if (a > 0){
            a = dfs(x, a, b);
        }
        else {
            if (b > 0){
                b = dfs(x, a, b);
            }
        }
    }
    if (ae) return a;
    return b;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    // cout << n << " " << a << " " << b << endl;
    res.assign(n, 3);
	int start = 0;
	graph.assign(n, vector<int>(0));
	vis.assign(n, false);
	int m = p.size();
	for (int i = 0; i < m; i++){
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
        cout << p[i] << " " << q[i] << endl;
	}

	for (int i = 0; i < n; i++){
        if (graph[i].size() < 2) start = i;
	}

	dfs(start, a, b);

	return res;
}

/*

6 5 2 2 2
0 1
1 2
2 3
3 4
4 5


*/

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