Submission #230066

#	Time	Username	Problem	Language	Result	Execution time	Memory
230066		Nightlight	Split the Attractions (IOI19_split)	C++14	0 / 100	399 ms	7928 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pib pair<int, bool>
#define mp make_pair
using namespace std;

set<int> adj[2505];
vector<int> ans;
int N, M;
pii id[5];
int cnt[5];
int dist[2505];
bool found;

void BFS(int a, int b) {
	queue<pii> q;
	q.push(mp(b, 2));
	q.push(mp(a, 1));
	memset(dist, 0, sizeof(dist));
	dist[a] = 1, dist[b] = 2;
  cnt[1] = 1, cnt[2] = 1;
	int u, lol;
	while(!q.empty()) {
		u = q.front().first;
		lol = q.front().second;
		q.pop();
		if(cnt[lol] == id[lol].first) continue;
		for(int v : adj[u]) {
			if(dist[v] == 0 && cnt[lol] < id[lol].first) {
				cnt[lol]++;
				dist[v] = lol;
				q.push(mp(v, lol));
			}
		}
	}
	if(cnt[1] >= id[1].first && cnt[2] >= id[2].first) {
		for(int i = 0; i < N; i++) {
			ans[i] = dist[i] == 0 ? id[3].second : id[dist[i]].second;
		}
		found = 1;
	} 
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n, id[1].first = a, id[2].first  = b, id[3].first = c, M = p.size();
	id[1].second = 1, id[2].second = 2, id[3].second = 3;
	sort(id + 1, id + 4);
	ans.resize(N);
	for(int i = 0; i < M; i++) {
		adj[p[i]].insert(q[i]);
		adj[q[i]].insert(p[i]);
	}
	for(int i = 0; i < M; i++) {
		adj[p[i]].erase(q[i]);
		adj[q[i]].erase(p[i]);
		BFS(p[i], q[i]);
		if(found) return ans;
		BFS(q[i], p[i]);
		if(found) return ans;
		adj[p[i]].insert(q[i]);
		adj[q[i]].insert(p[i]);
	}
	return ans;
}

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