답안 #410780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410780	2021-05-23T17:49:51 Z	AmineWeslati	Amusement Park (JOI17_amusement_park)	C++14	78 / 100	35 ms	6516 KB

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi; 
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//------------------------------------------------//

const int MX=2e4+10;
const int LOG=60;

bitset<LOG>b; 
vi nei[MX];

vi par(MX),adj[MX],bit(MX),val(MX);
int cnt=-1;

vi viss(MX,0);

void dfs(int u, int p){
	viss[u]=1;
	par[u]=p;

	bit[u]=++cnt; bit[u]%=LOG;
	val[u]=b[bit[u]];

	for(int v: nei[u]) if(!viss[v]){
		adj[u].pb(v);
		dfs(v,u);
	}
}

void Joi(int N, int M, int A[], int B[], ll X, int T){
	FOR(i,0,M){
		int u=A[i],v=B[i];
		nei[u].pb(v);
		nei[v].pb(u);
	}
	FOR(i,0,LOG){
		b[i]=X%2;
		X/=2;
	}

	dfs(0,0);	

	FOR(i,0,N) MessageBoard(i,val[i]);
}

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

typedef long long ll;
typedef vector<int>vi; 
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//------------------------------------------------//

const int MX=2e4+10;
const int LOG=60;

vi nei2[MX];

vi par2(MX),adj2[MX],bit2(MX);
int cnt2=-1;

vi visss(MX,0);
void dfs2(int u, int p){
	visss[u]=1;
	par2[u]=p;

	bit2[u]=++cnt2; bit2[u]%=LOG;

	for(int v: nei2[u]) if(!visss[v]){
		adj2[u].pb(v);
		dfs2(v,u);
	}
}

vi ans(LOG),vis(MX,0);
set<int>s;

void explore(int u, int x){
	vis[u]=1;
	s.insert(bit2[u]);
	ans[bit2[u]]=x; 

	if(sz(s)>=LOG) return; 

	int all=1,none=1;
	for(int v: adj2[u]){
		if(!vis[v]) all=0;
		if(vis[v]) none=0;
	}

	if(all){
		assert(u!=0);
		explore(par2[u],Move(par2[u]));
	}
	else if(none){
		explore(adj2[u][0],Move(adj2[u][0]));
	}
	else{
		int idx=-1;
		FOR(i,0,sz(adj2[u])) if(vis[adj2[u][i]]){
			idx=i;
			while(vis[adj2[u][idx]]){
				idx++; 
				idx%=sz(adj2[u]);
			}
			break;
		}
		assert(idx!=-1);

		explore(adj2[u][idx],Move(adj2[u][idx]));
	}
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	FOR(i,0,M){
		int u=A[i],v=B[i];
		nei2[u].pb(v);
		nei2[v].pb(u);
	}
	dfs2(0,0);

	explore(P,V);

	ll x=0;
	ROF(i,0,LOG){
		x*=2;
		x+=ans[i];
	}
	return x;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3048 KB	Output is correct
2	Correct	3 ms	3052 KB	Output is correct
3	Correct	3 ms	3052 KB	Output is correct
4	Correct	2 ms	3048 KB	Output is correct
5	Correct	4 ms	3048 KB	Output is correct
6	Correct	4 ms	3048 KB	Output is correct
7	Correct	3 ms	3052 KB	Output is correct
8	Correct	3 ms	3052 KB	Output is correct
9	Correct	4 ms	3056 KB	Output is correct
10	Correct	3 ms	3044 KB	Output is correct
11	Correct	6 ms	3480 KB	Output is correct
12	Correct	2 ms	3124 KB	Output is correct
13	Correct	3 ms	3052 KB	Output is correct
14	Correct	3 ms	3052 KB	Output is correct
15	Correct	4 ms	3060 KB	Output is correct
16	Correct	4 ms	3056 KB	Output is correct
17	Correct	3 ms	3060 KB	Output is correct
18	Correct	3 ms	3052 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	6256 KB	Output is correct
2	Correct	28 ms	6404 KB	Output is correct
3	Correct	28 ms	6516 KB	Output is correct
4	Correct	17 ms	4908 KB	Output is correct
5	Correct	19 ms	5720 KB	Output is correct
6	Correct	20 ms	5300 KB	Output is correct
7	Correct	20 ms	5276 KB	Output is correct
8	Correct	20 ms	5404 KB	Output is correct
9	Correct	18 ms	5364 KB	Output is correct
10	Correct	15 ms	4776 KB	Output is correct
11	Correct	16 ms	4740 KB	Output is correct
12	Correct	16 ms	4632 KB	Output is correct
13	Correct	16 ms	4632 KB	Output is correct
14	Correct	17 ms	4780 KB	Output is correct
15	Correct	24 ms	5044 KB	Output is correct
16	Correct	20 ms	5040 KB	Output is correct
17	Correct	20 ms	4920 KB	Output is correct
18	Correct	18 ms	4972 KB	Output is correct
19	Correct	18 ms	4992 KB	Output is correct
20	Correct	15 ms	5404 KB	Output is correct
21	Correct	14 ms	5420 KB	Output is correct
22	Correct	18 ms	5120 KB	Output is correct
23	Correct	18 ms	5284 KB	Output is correct
24	Correct	18 ms	5164 KB	Output is correct
25	Correct	18 ms	5188 KB	Output is correct
26	Correct	18 ms	5300 KB	Output is correct
27	Correct	18 ms	5340 KB	Output is correct
28	Correct	24 ms	5220 KB	Output is correct
29	Correct	17 ms	5132 KB	Output is correct
30	Correct	17 ms	5160 KB	Output is correct
31	Correct	2 ms	3048 KB	Output is correct
32	Correct	3 ms	3044 KB	Output is correct
33	Correct	4 ms	3052 KB	Output is correct
34	Correct	4 ms	3048 KB	Output is correct
35	Correct	2 ms	3048 KB	Output is correct
36	Correct	3 ms	3048 KB	Output is correct
37	Correct	2 ms	3048 KB	Output is correct
38	Correct	2 ms	3048 KB	Output is correct
39	Correct	3 ms	3052 KB	Output is correct
40	Correct	3 ms	3056 KB	Output is correct
41	Correct	3 ms	3052 KB	Output is correct
42	Correct	3 ms	3052 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3048 KB	Output is correct
2	Correct	3 ms	3048 KB	Output is correct
3	Correct	2 ms	3060 KB	Output is correct
4	Correct	5 ms	3588 KB	Output is correct
5	Correct	5 ms	3588 KB	Output is correct
6	Correct	5 ms	3588 KB	Output is correct
7	Correct	4 ms	3596 KB	Output is correct
8	Correct	6 ms	3588 KB	Output is correct
9	Correct	19 ms	6320 KB	Output is correct
10	Correct	16 ms	6356 KB	Output is correct
11	Correct	16 ms	6292 KB	Output is correct
12	Correct	2 ms	3048 KB	Output is correct
13	Correct	3 ms	3048 KB	Output is correct
14	Correct	2 ms	3048 KB	Output is correct
15	Correct	2 ms	3048 KB	Output is correct

Subtask #4
50.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	6304 KB	Output is correct
2	Partially correct	35 ms	6308 KB	Partially correct
3	Correct	28 ms	6304 KB	Output is correct
4	Correct	17 ms	4844 KB	Output is correct
5	Correct	19 ms	5920 KB	Output is correct
6	Correct	20 ms	5552 KB	Output is correct
7	Correct	18 ms	5420 KB	Output is correct
8	Correct	17 ms	5144 KB	Output is correct
9	Correct	23 ms	5296 KB	Output is correct
10	Correct	22 ms	4704 KB	Output is correct
11	Correct	19 ms	4792 KB	Output is correct
12	Correct	19 ms	4684 KB	Output is correct
13	Correct	16 ms	4728 KB	Output is correct
14	Correct	17 ms	4688 KB	Output is correct
15	Correct	17 ms	5044 KB	Output is correct
16	Correct	18 ms	5032 KB	Output is correct
17	Correct	17 ms	4836 KB	Output is correct
18	Correct	18 ms	4964 KB	Output is correct
19	Correct	18 ms	4912 KB	Output is correct
20	Correct	15 ms	5440 KB	Output is correct
21	Correct	14 ms	5368 KB	Output is correct
22	Correct	17 ms	5252 KB	Output is correct
23	Correct	20 ms	5300 KB	Output is correct
24	Correct	18 ms	5164 KB	Output is correct
25	Correct	18 ms	5240 KB	Output is correct
26	Correct	24 ms	5260 KB	Output is correct
27	Correct	18 ms	5416 KB	Output is correct
28	Correct	19 ms	5168 KB	Output is correct
29	Correct	17 ms	5108 KB	Output is correct
30	Correct	17 ms	5244 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	6312 KB	Output is correct
2	Correct	28 ms	6396 KB	Output is correct
3	Correct	28 ms	6312 KB	Output is correct
4	Incorrect	20 ms	4876 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

답안 #410780

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 50.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
50.0 / 55.0

Subtask #5
0 / 17.0