oj.uz

Submission #298437

# Submission time Handle Problem Language Result Execution time Memory
298437 2020-09-12T21:03:56 Z pit4h Amusement Park (JOI17_amusement_park) C++14
0 / 100
 16 ms 4896 KB 
#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 {
		assert(false);
		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]);
	}
}
#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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 4864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 4864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 4896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -