Submission #792201

#	Time	Username	Problem	Language	Result	Execution time	Memory
792201		APROHACK	Split the Attractions (IOI19_split)	C++17	11 / 100	75 ms	17324 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;
int dp(int u){
	vis[u] = true;
	int minimo = INT_MAX;
	if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){
		mejor = abajo[u] + 1;
		donde = u;
		minimo = abajo[u] + 1;
		//cout << "new best " << u << endl;
	}
	for(int i = 0 ; i < adj[u].size() ; i ++){
		if(vis[adj[u][i]])continue;
		minimo = min ( minimo, dp(adj[u][i]));
	}
	if(A - (abajo[u] + 1) > 0)return minimo;
	else return min ( minimo, (abajo[u] + 1) );
}

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 --;
	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 ;
	}	
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int>all0;
	for(int i = 0 ; i < n ; i ++)all0.pb(0);
	N = n;
	m = p.size();
	for(int i = 0 ; i < m ; i ++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	memset(vis, false, sizeof vis);
	dfs(0);
	//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;
	for(int i = 0 ; i < n ; i++)respuesta.pb(0);
	memset(vis, false, sizeof vis);
	if(dp(0) == INT_MAX){
		return all0;
	}
	
	int restantes = A - 1;
	memset(vis, false, sizeof vis);
	vis[donde] = true;
	int parent = -1;
	for(auto i : adj[donde]){
		if(abajo[i] > abajo[donde]){
			parent = i;
			continue;
		}
		generarSubArbol(i, 1, restantes);
		if(restantes <= 0 )break;
	}
	if(parent==-1)return all0;
	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;
}

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 'int dp(int)':
split.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void generarSubArbol(int, int, int&)':
split.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~

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