Submission #298439

#	Time	Username	Problem	Language	Result	Execution time	Memory
298439		pit4h	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	219 ms	23000 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int _B = 60;
void build_tree(int x, vector<vector<int>>& g, vector<bool>& vis, vector<vector<int>>& G) {
	vis[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			G[x].push_back(i);
			G[i].push_back(x);
			build_tree(i, g, vis, G);
		}
	}
}
struct Nodes {
	int key, val, par;	
};
void dfs(int x, int p, vector<vector<int>>& g, int& counter, vector<vector<Nodes>>& T, vector<int>& rep) {
	if(counter<_B) {
		T[0].push_back({x, counter, p});	
		rep[x] = 0;
	}
	else {
		rep[x] = T.size();
		T.push_back(T[rep[p]]);
		map<int, bool> has_child;
		for(auto it: T[rep[x]]) {
			has_child[it.par] = 1;
		}
		bool fail=1;
		for(auto &it: T[rep[x]]) {
			if(it.key != p && !has_child[it.key]) {
				it.key = x;
				it.par = p;
				fail = 0;
				break;
			}
		}
		if(fail) { // delete root
			int root;
			for(auto &it: T[rep[x]]) {
				if(it.par == -1) {
					root = it.key;
					it.key = x;
					it.par = p;
				}
			}
			for(auto &it: T[rep[x]]) {
				if(it.par == root) {
					it.par = -1;
				}
			}
		}
	}
	counter++;
	for(int i: g[x]) {
		if(i!=p) {
			dfs(i, x, g, counter, T, rep);
		}
	}
}
void Joi(int N, int M, int A[], int B[], ll X, int T) {
	// MessageBoard();
	vector<vector<int>> g(N), G(N);
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	vector<bool> vis(N);
	build_tree(0, g, vis, G);
	vector<vector<Nodes>> Tree(1);
	int counter = 0;
	vector<int> rep(N);
	dfs(0, -1, G, counter, Tree, rep);	
	vector<int> value(N);
	for(auto t: Tree) {
		for(auto it: t) {
			value[it.key] = (bool)(X&(1LL<<it.val));
		}
	}
	for(int i=0; i<N; ++i) {
		MessageBoard(i, value[i]);
	}
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int bits = 60;
void _build_tree(int x, vector<vector<int>>& g, vector<bool>& vis, vector<vector<int>>& G) {
	vis[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			G[x].push_back(i);
			G[i].push_back(x);
			_build_tree(i, g, vis, G);
		}
	}
}
struct _Nodes {
	int key, val, par;	
};
void _dfs(int x, int p, vector<vector<int>>& g, int& counter, vector<vector<_Nodes>>& T, vector<int>& rep) {
	if(counter<bits) {
		T[0].push_back({x, counter, p});	
		rep[x] = 0;
	}
	else {
		rep[x] = T.size();
		T.push_back(T[rep[p]]);
		map<int, bool> has_child;
		for(auto it: T[rep[x]]) {
			has_child[it.par] = 1;
		}
		bool fail=1;
		for(auto &it: T[rep[x]]) {
			if(it.key != p && !has_child[it.key]) {
				it.key = x;
				it.par = p;
				fail = 0;
				break;
			}
		}
		if(fail) { // delete root
			int root;
			for(auto &it: T[rep[x]]) {
				if(it.par == -1) {
					root = it.key;
					it.key = x;
					it.par = p;
				}
			}
			for(auto &it: T[rep[x]]) {
				if(it.par == root) {
					it.par = -1;
				}
			}
		}
	}
	counter++;
	for(int i: g[x]) {
		if(i!=p) {
			_dfs(i, x, g, counter, T, rep);
		}
	}
}
void solve(int x, int prv, int v, vector<vector<int>>& g, vector<bool>& vis, vector<int>& value, ll& X) {
	vis[x] = 1;
	X += (ll)v * (1LL<<value[x]);
	for(int i: g[x]) {
		if(!vis[i]) {
			solve(i, x, Move(i), g, vis, value, X);
		}
	}
	if(prv != -1) {
		Move(prv);
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	vector<vector<int>> g(N), G(N);
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	vector<bool> vis(N);
	_build_tree(0, g, vis, G);
	vector<vector<_Nodes>> Tree(1);
	int counter = 0;
	vector<int> rep(N);
	_dfs(0, -1, G, counter, Tree, rep);
	vis = vector<bool>(N, 1);
	vector<int> value(N);
	for(auto it: Tree[rep[P]]) {
		vis[it.key] = 0;
		value[it.key] = it.val;
	}
	ll X = 0;
	solve(P, -1, V, G, vis, value, X);
	return X;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, int&, std::vector<std::vector<Nodes> >&, std::vector<int>&)':
Joi.cpp:50:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     if(it.par == root) {
      |     ^~

Ioi.cpp: In function 'void _dfs(int, int, std::vector<std::vector<int> >&, int&, std::vector<std::vector<_Nodes> >&, std::vector<int>&)':
Ioi.cpp:50:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     if(it.par == root) {
      |     ^~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17