oj.uz

Submission #514080

# Submission time Handle Problem Language Result Execution time Memory
514080 2022-01-18T03:17:45 Z amunduzbaev Amusement Park (JOI17_amusement_park) C++14
0 / 100
 26 ms 4648 KB 
#include "bits/stdc++.h"
using namespace std;
#include "Joi.h"

//~ #ifndef EVAL
//~ #include "grader.cpp"
//~ #endif
//~ int a[20005];

//~ void MessageBoard(int x, int v){
	//~ a[x] = v;
//~ }

//~ int Move(int x){
	//~ return a[x];
//~ }

//~ namespace JOI{
	const int NN = 1e4 + 5;
	vector<int> G[NN], tt;
	int used[NN], d[NN];

	void dfs(int u){
		used[u] = 1;
		tt.push_back(u);
		for(auto x : G[u]){
			if(used[x]) continue;
			d[x] = d[u] + 1;
			dfs(x);
		}
	}

	void Joi(int n, int m, int a[], int b[], long long x, int t) {
		for(int i=0;i<m;i++){
			G[a[i]].push_back(b[i]);
			G[b[i]].push_back(a[i]);
		} for(int i=0;i<n;i++){
			sort(G[i].begin(), G[i].end());
		}
		d[0] = 1;
		dfs(0);
		bool ok = 0;
		for(int i=0;i<n;i++){
			if(d[i] >= 60){
				ok = 1;
			}
		}
		
		if(ok){
			for(int i=0;i<n;i++){ d[i] = (d[i] - 1) % 60;
				MessageBoard(i, x >> d[i] & 1);
			}
		} else {
			for(int i=0;i<60;i++){
				MessageBoard(tt[i], x >> i & 1);
			} for(int i=60;i<n;i++){
				MessageBoard(tt[i], 0);
			}
		}
	}
//~ }

//~ namespace IOI{
	
	//~ const int NN = 1e4 + 5;
	//~ vector<int> G[NN], tt;
	//~ int used[NN], par[NN], d[NN];

	//~ void dfs(int u){
		//~ used[u] = 1;
		//~ tt.push_back(u);
		//~ for(auto x : G[u]){
			//~ if(used[x]) continue;
			//~ d[x] = d[u] + 1, 
			//~ par[x] = u, dfs(x);
			//~ tt.push_back(u);
		//~ }
	//~ }

	//~ long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
		//~ for(int i=0;i<m;i++){
			//~ G[a[i]].push_back(b[i]);
			//~ G[b[i]].push_back(a[i]);
		//~ }
		
		//~ for(int i=0;i<n;i++) sort(G[i].begin(), G[i].end());
		//~ d[0] = 1;
		//~ dfs(0);
		//~ bool ok = 0;
		//~ int r = 0;
		//~ for(int i=0;i<n;i++){
			//~ if(d[i] >= 60) ok = 1, r = i;
		//~ }
		//~ long long x = 0;
		//~ if(ok){
			//~ if(d[p] >= 60){
				//~ for(int j=0;j<60;j++){ d[p] = (d[p] - 1) % 60;
					//~ x |= ((v * 1ll) << d[p]);
					//~ if(p) v = Move(par[p]), p = par[p];
				//~ } return x;
			//~ } else {
				//~ while(p) v = Move(par[p]), p = par[p];
				//~ vector<int> tt;
				//~ while(r) tt.push_back(r), r = par[r];
				//~ for(int i=0;i<60;i++){ d[p] = (d[p] - 1) % 60;
					//~ x |= ((v * 1ll) << d[p]);
					//~ if(!tt.empty()){
						//~ v = Move(tt.back()), p = tt.back(); 
						//~ tt.pop_back();
					//~ }
				//~ } return x;
			//~ }
		//~ }
		
		//~ while(p) v = Move(par[p]), p = par[p];
		//~ memset(used, 0, sizeof used);
		//~ int cnt = 60;
		//~ assert(!tt[0]);
		
		//~ for(auto u : tt){
			//~ if(u != p) p = u, v = Move(u);
			//~ if(used[u]) continue;
			//~ used[u] = 1;
			//~ x |= ((v * 1ll) << (cnt - 1));
			//~ cnt++;
			//~ if(cnt == 60) break;
		//~ } return x;
	//~ }

//~ }

//~ signed main(){
	//~ freopen("sample-01.txt", "r", stdin);
	//~ int n, m, x, p, t; cin>>n>>m>>x>>p>>t;
	//~ int a[20005], b[20005];
	//~ for(int i=0;i<m;i++){
		//~ cin>>a[i]>>b[i];
	//~ }
	
	//~ JOI::Joi(n, m, a, b, x, t);
	//~ long long res = IOI::Ioi(n, m, a, b, p, ::a[p], t);
	//~ cout<<res<<" "<<x<<"\n";
//~ }

#include "bits/stdc++.h"
using namespace std;
#include "Ioi.h"

//~ #ifndef EVAL
//~ #include "grader.cpp"
//~ #endif

const int NN = 1e4 + 5;
vector<int> G[NN], tt;
int used[NN], par[NN], d[NN];

void dfs(int u){
	used[u] = 1;
	tt.push_back(u);
	for(auto x : G[u]){
		if(used[x]) continue;
		d[x] = d[u] + 1, 
		par[x] = u, dfs(x);
		tt.push_back(u);
	}
}

long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
	for(int i=0;i<m;i++){
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	}
	
	for(int i=0;i<n;i++) sort(G[i].begin(), G[i].end());
	d[0] = 1;
	dfs(0);
	bool ok = 0;
	int r = 0;
	for(int i=0;i<n;i++){
		if(d[i] >= 60) ok = 1, r = i;
	}
	
	long long x = 0;
	if(ok){
		if(d[p] >= 60){
			for(int j=0;j<60;j++){ d[p] = (d[p] - 1) % 60;
				x |= ((v * 1ll) << d[p]);
				if(p) v = Move(par[p]), p = par[p];
			} return x;
		} else {
			while(p) v = Move(par[p]), p = par[p];
			vector<int> tt;
			while(r) tt.push_back(r), r = par[r];
			for(int i=0;i<60;i++){ d[p] = (d[p] - 1) % 60;
				x |= ((v * 1ll) << d[p]);
				if(tt.empty()){
					v = Move(tt.back()), p = tt.back(); 
					tt.pop_back();
				}
			} return x;
		}
	}
	
	while(p) v = Move(par[p]), p = par[p];
	memset(used, 0, sizeof used);
	int cnt = 60;
	assert(!tt[0]);
	
	for(auto u : tt){
		if(u != p) p = u, v = Move(u);
		if(used[u]) continue;
		used[u] = 1;
		x |= ((v * 1ll) << (cnt - 1));
		cnt++;
		if(cnt == 60) break;
	} return x;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1136 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4544 KB Output is correct
2 Correct 26 ms 4648 KB Output is correct
3 Correct 26 ms 4476 KB Output is correct
4 Incorrect 19 ms 2992 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1000 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4528 KB Output is correct
2 Correct 22 ms 4544 KB Output is correct
3 Correct 25 ms 4568 KB Output is correct
4 Incorrect 19 ms 2932 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4532 KB Output is correct
2 Correct 20 ms 4496 KB Output is correct
3 Correct 22 ms 4524 KB Output is correct
4 Incorrect 17 ms 2968 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -