Submission #169935

#	Time	Username	Problem	Language	Result	Execution time	Memory
169935		socho	Split the Attractions (IOI19_split)	C++14	0 / 100	8 ms	5752 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(node);
	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);
	
	// cout << fmost << " for A" << endl;
	
	vector<int> re(n);
	re[fmost] = 1;
	blocked[fmost] = true;
	
	limit = b;
	took = 0;
	int sta = adj[fmost].front();
	travel(sta);
	
	assert(taken.size() == b);
	
	for (int i=0; i<b; i++) {
		// cout << taken[i] << " for B" << endl;
		re[taken[i]] = 2;
	}
	
	for (int i=0; i<n; i++) {
		if (re[i] == 0) {
			// cout << i << " for C" << endl;
			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++) {
                ~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(taken.size() == b);
         ~~~~~~~~~~~~~^~~~

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