oj.uz

Submission #197806

# Submission time Handle Problem Language Result Execution time Memory
197806 2020-01-23T09:29:32 Z TAISA_ Amusement Park (JOI17_amusement_park) C++14
10 / 100
 36 ms 5444 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
static vector<vector<int>> G;
static vector<int> vis,dep,et;
static int md;
static void dfs(int i){
	vis[i]=1;
	md=max(md,dep[i]);
	et.push_back(i);
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		dep[e]=dep[i]+1;
		dfs(e);
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	G.resize(N);
	vis.resize(N);
	dep.resize(N);
	for(int i=0;i<M;i++){
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	dfs(0);
	if(md>=59){
		for(int i=0;i<N;i++){
			dep[i]%=60;
			MessageBoard(i,((X>>dep[i])&1));
		}
	}else{
		for(int i=0;i<N;i++){
			if(i<60){
				MessageBoard(et[i],((X>>i)&1));
			}else{
				MessageBoard(et[i],0);
			}
		}
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
static vector<vector<int>> G,g;
static vector<int> vis,dep,et,md,par,res;
static int dfs(int i){
	vis[i]=1;
	md[i]=dep[i];
	et.push_back(i);
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		g[i].push_back(e);
		dep[e]=dep[i]+1;
		par[e]=i;
		md[i]=max(md[i],dfs(e));
	}
	return md[i];
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	G.resize(N);
	g.resize(N);
	vis.resize(N);
	dep.resize(N);
	md.resize(N);
	for(int i=0;i<M;i++){
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	par.resize(N,-1);
	res.resize(N,-1);
	dfs(0);
	ll ans=0;
	if(md[0]>=59){
		while(dep[P]%60>0){
			res[par[P]]=Move(par[P]);
			P=par[P];
		}
		vector<int> vs;
		if(md[P]-dep[P]<59){
			while(md[P]-dep[P]<59||dep[P]%60>0){
				res[par[P]]=Move(par[P]);
				vs.push_back(res[par[P]]);
				P=par[P];
			}
			reverse(vs.begin(),vs.end());
		}else{
			int r=P;
			while(P==r||dep[P]%60>0){
				vs.push_back(res[P]);
				if(g[P].empty()){
					break;
				}
				for(auto &e:g[P]){
					if(md[e]-dep[r]>=59){
						res[e]=Move(e);
						P=e;
						break;
					}
				}
			}
		}
		for(int i=0;i<60;i++){
			if(vs[i]){
				ans+=(1LL<<i);
			}
		}		
	}else{
		while(P>0){
			Move(par[P]);
			P=par[P];
		}
		
	}
	return ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4928 KB Output is correct
2 Correct 34 ms 5136 KB Output is correct
3 Correct 34 ms 5292 KB Output is correct
4 Incorrect 20 ms 3756 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 900 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 884 KB Output is correct
4 Correct 6 ms 1588 KB Output is correct
5 Correct 6 ms 1456 KB Output is correct
6 Correct 6 ms 1476 KB Output is correct
7 Correct 6 ms 1456 KB Output is correct
8 Correct 7 ms 1660 KB Output is correct
9 Correct 19 ms 5004 KB Output is correct
10 Correct 18 ms 4904 KB Output is correct
11 Correct 18 ms 4784 KB Output is correct
12 Correct 4 ms 748 KB Output is correct
13 Correct 4 ms 1000 KB Output is correct
14 Correct 4 ms 896 KB Output is correct
15 Correct 3 ms 876 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4944 KB Output is correct
2 Correct 35 ms 5444 KB Output is correct
3 Correct 35 ms 5272 KB Output is correct
4 Incorrect 23 ms 3752 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4824 KB Output is correct
2 Correct 35 ms 5144 KB Output is correct
3 Correct 36 ms 5268 KB Output is correct
4 Incorrect 20 ms 3960 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -