Submission #792268

#	Time	Username	Problem	Language	Result	Execution time	Memory
792268		APROHACK	Split the Attractions (IOI19_split)	C++17	40 / 100	80 ms	15912 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
vector<int>adj[100005];
int N, m;
bool vis[100005];
int abajo[100005], maximo[100005];
int dfs(int u){
	vis[u] = true;
	abajo[u] = 0;
	maximo[u] = 0;
	int cu = 0;
	for(int i = 0 ; i < adj[u].size() ; i ++){
		if(vis[adj[u][i]]){
			continue;
		}
		cu = dfs(adj[u][i]);
		abajo[u] += cu;
		maximo[u] = max(maximo[u], cu);
	}
	return abajo[u] + 1;
}
vector<int> respuesta;
int A, B;
int mejor, donde;
void dp(int u){
	vis[u] = true;
	if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){
		mejor = abajo[u] + 1;
		donde = u;
		//cout << "new best " << u << endl;
	}
	for(int i = 0 ; i < adj[u].size() ; i ++){
		if(vis[adj[u][i]])continue;
		dp(adj[u][i]);
	}
}

void generarSubArbol(int u, int val, int &restantes){
	//cout << "generando " << u << " val " << val << " res " << restantes << endl;
	if(restantes <= 0){
		return ;
	}
	vis [ u ] = true;
	respuesta[u] = val;
	restantes --;
	if(restantes <= 0)return ;
	for(int i = 0 ; i < adj[u].size() ; i ++){
		if(vis[adj[u][i]])continue;
		generarSubArbol(adj[u][i], val, restantes);
		if(restantes <= 0)return ;
	}	
}


int bfs(int st){
	queue<int>cola;
	memset(vis, false, sizeof vis);
	cola.push(st);
	int distancia[N+3];
	vis[st] = true;
	distancia[st] = 0;
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(vis[adj[cur][i]])continue;
			cola.push(adj[cur][i]);
			vis[adj[cur][i]] = true;
			distancia[adj[cur][i]] = distancia[cur] + 1;
		}
	}
	int hoja, dist = 0;
	for(int i = 0 ; i < N ; i ++){
		if(distancia[i] > dist)hoja = i, dist = distancia[i];
	}
	return hoja;
}

vector<int> test(int root, int a, int b, int c){
	int n = N;
	vector<int>all0;
	for(int i = 0 ; i < n ; i ++)all0.pb(0);
	memset(vis, false, sizeof vis);
	dfs(root);
	//for(int i = 0 ; i < n ; i ++)cout << abajo[i] << endl; 
	//cout << endl;
	vector<int> opt;
	opt.pb(a);
	opt.pb(b);
	opt.pb(c);
	sort(opt.begin(), opt.end());
	A = opt[0];
	B = opt[1];
	mejor = INT_MAX;
	donde = root;
	respuesta.clear();
	for(int i = 0 ; i < n ; i++)respuesta.pb(0);
	memset(vis, false, sizeof vis);
	dp(root);
	if(donde == root)return all0;
	int restantes = A - 1;
	memset(vis, false, sizeof vis);
	vis[donde] = true;
	int parent = root;
	for(auto i : adj[donde]){
		if(abajo[i] >= abajo[donde]){
			continue;
		}
		generarSubArbol(i, 1, restantes);
		if(restantes <= 0 )break;
	}
	respuesta[donde] = 1;
	restantes = B;
	//cout << "donde " << donde << " parent " << parent << endl;
	generarSubArbol(parent, 2, restantes);
	if(restantes > 0)return all0;
	for(int i = 0 ; i < n ; i ++)if(respuesta[i] == 0)respuesta[i] = 3;
	int mapeo[4];
	bool banned[3];
	memset(banned, false, sizeof banned);
	for(int i = 0 ; i < 3 ; i ++){
		if(opt[i] == a and !banned[0]){
			banned[0] = true;
			mapeo[i+1] = 1;
		}else if(opt[i] == b and !banned[1]){
			banned[1] = true;
			mapeo[i+1] = 2;
		}else{
			banned[2] = true;
			mapeo[i+1] = 3;
		}
	}
	for(int i = 0 ; i < n ; i++){
		respuesta[i] = mapeo[respuesta[i]];
	}
	return respuesta;
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	m = p.size();
	for(int i = 0 ; i < m ; i ++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	int rootA = bfs(0), rootB = bfs(rootA);
	vector<int>respA = test(rootA, a, b, c);
	if(respA[0] != 0){
		return respA;
	}else return test(rootB, a, b, c);
}

Compilation message (stderr)

split.cpp: In function 'int dfs(int)':
split.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dp(int)':
split.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void generarSubArbol(int, int, int&)':
split.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'int bfs(int)':
split.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
split.cpp:81:9: warning: 'hoja' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |  return hoja;
      |         ^~~~

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