oj.uz

답안 #197807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197807 2020-01-23T09:34:35 Z TAISA_ Amusement Park (JOI17_amusement_park) C++14
10 / 100
 37 ms 4956 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];
}
static int cnt;
static void dfs2(int i){
	vis[i]=1;
	cnt++;
	if(cnt==60){
		return;
	}
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		res[e]=Move(e);
		dfs2(e);
		if(cnt==60){
			return;
		}
	}
	Move(par[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;
	res[P]=V;
	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];
		}
		vis.assign(N,0);
		cnt=0;
		dfs2(0);
		for(int i=0;i<60;i++){
			if(res[et[i]]){
				ans+=(1LL<<i);
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 892 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4904 KB Output is correct
2 Correct 35 ms 4944 KB Output is correct
3 Correct 35 ms 4944 KB Output is correct
4 Correct 20 ms 3512 KB Output is correct
5 Correct 23 ms 4264 KB Output is correct
6 Correct 27 ms 4144 KB Output is correct
7 Correct 22 ms 4328 KB Output is correct
8 Correct 22 ms 4144 KB Output is correct
9 Correct 22 ms 4200 KB Output is correct
10 Correct 19 ms 3844 KB Output is correct
11 Correct 19 ms 3848 KB Output is correct
12 Correct 23 ms 3696 KB Output is correct
13 Correct 20 ms 3472 KB Output is correct
14 Correct 20 ms 3660 KB Output is correct
15 Correct 23 ms 3820 KB Output is correct
16 Correct 20 ms 3736 KB Output is correct
17 Correct 22 ms 3624 KB Output is correct
18 Correct 23 ms 3852 KB Output is correct
19 Correct 20 ms 3880 KB Output is correct
20 Correct 18 ms 4136 KB Output is correct
21 Correct 18 ms 4212 KB Output is correct
22 Correct 23 ms 4008 KB Output is correct
23 Correct 23 ms 4244 KB Output is correct
24 Correct 22 ms 4060 KB Output is correct
25 Correct 22 ms 3880 KB Output is correct
26 Correct 22 ms 4144 KB Output is correct
27 Correct 22 ms 4136 KB Output is correct
28 Correct 22 ms 4008 KB Output is correct
29 Correct 20 ms 3856 KB Output is correct
30 Correct 22 ms 3876 KB Output is correct
31 Correct 4 ms 892 KB Output is correct
32 Correct 4 ms 828 KB Output is correct
33 Incorrect 4 ms 900 KB Wrong Answer [7]
34 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 880 KB Output is correct
2 Correct 9 ms 888 KB Output is correct
3 Correct 4 ms 880 KB Output is correct
4 Correct 6 ms 1432 KB Output is correct
5 Correct 6 ms 1300 KB Output is correct
6 Correct 6 ms 1168 KB Output is correct
7 Correct 6 ms 1432 KB Output is correct
8 Correct 6 ms 1560 KB Output is correct
9 Correct 18 ms 4672 KB Output is correct
10 Correct 18 ms 4544 KB Output is correct
11 Correct 18 ms 4536 KB Output is correct
12 Correct 4 ms 880 KB Output is correct
13 Correct 4 ms 752 KB Output is correct
14 Correct 4 ms 880 KB Output is correct
15 Correct 4 ms 880 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4956 KB Output is correct
2 Correct 34 ms 4816 KB Output is correct
3 Correct 36 ms 4808 KB Output is correct
4 Incorrect 23 ms 3520 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 4824 KB Output is correct
2 Correct 36 ms 4944 KB Output is correct
3 Correct 37 ms 4940 KB Output is correct
4 Correct 24 ms 3608 KB Output is correct
5 Correct 25 ms 4660 KB Output is correct
6 Correct 23 ms 4052 KB Output is correct
7 Correct 24 ms 4012 KB Output is correct
8 Correct 24 ms 4136 KB Output is correct
9 Correct 23 ms 4224 KB Output is correct
10 Correct 19 ms 3756 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 20 ms 3600 KB Output is correct
13 Incorrect 20 ms 3356 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -