Submission #169933

#	Time	Username	Problem	Language	Result	Execution time	Memory
169933		socho	Split the Attractions (IOI19_split)	C++14	0 / 100	4 ms	2936 KiB

split

#include "bits/stdc++.h"
#include "split.h"
using namespace std;

int A, B, C, N;
const int MXN = 100005;
vector<int> adj[MXN];
int res[MXN];
int dist[MXN];
bool vis[MXN];

void bfs_dist(int source) {
	
	memset(vis, 0, sizeof vis);
	queue<pair<int, int> > proc;
	for (int i=0; i<N; i++) dist[i] = INT_MAX;
	proc.push(make_pair(source, 0)); // node, distance
	while (!proc.empty()) {
		int node = proc.front().first, dis = proc.front().second;
		proc.pop();
		if (dist[node] < dis) {
			continue;
		}
		dist[node] = dis;
		int po = dis + 1;
		for (int i=0; i<adj[node].size(); i++) {
			int ot = adj[node][i];
			if (dist[ot] > po) {
				dist[ot] = po;
				proc.push(make_pair(ot, po));
			}
		}
	}
	
}

int limit = 0;
int took = 0;
vector<int> taken;
bool blocked[MXN];

void travel(int node) {
	if (took >= limit) return;
	taken.push_back(took);
	took++;
	blocked[node] = true;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (blocked[ot]) continue;
		travel(ot);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	A = a;
	B = b;
	C = c;
	N = n;
	for (int i=0; i<n-1; i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	
	bfs_dist(0);
	int furthest = max_element(dist, dist+n) - dist;
	bfs_dist(furthest);
	int fmost = max_element(dist, dist+n) - dist;
	
	memset(blocked, 0, sizeof blocked);
	
	vector<int> re(n);
	re[fmost] = 1;
	blocked[fmost] = true;
	
	limit = b;
	took = 0;
	int sta = adj[fmost].front();
	travel(sta);
	
	for (int i=0; i<b; i++) {
		re[taken[i]] = 2;
	}
	
	for (int i=0; i<n; i++) {
		if (re[i] == 0) re[i] = 3;
	}
	
	return re;
}

Compilation message (stderr)

split.cpp: In function 'void bfs_dist(int)':
split.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<adj[node].size(); i++) {
                 ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void travel(int)':
split.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~

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