oj.uz

Submission #410778

# Submission time Handle Problem Language Result Execution time Memory
410778 2021-05-23T17:46:48 Z AmineWeslati Amusement Park (JOI17_amusement_park) C++14
50 / 100
 34 ms 6416 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(u==0) assert(sz(s)==LOG);

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3056 KB Output is correct
2 Correct 2 ms 3056 KB Output is correct
3 Correct 3 ms 3060 KB Output is correct
4 Correct 2 ms 3052 KB Output is correct
5 Correct 2 ms 3048 KB Output is correct
6 Correct 3 ms 3060 KB Output is correct
7 Correct 3 ms 3056 KB Output is correct
8 Correct 4 ms 3056 KB Output is correct
9 Correct 3 ms 3052 KB Output is correct
10 Correct 2 ms 3048 KB Output is correct
11 Correct 7 ms 3480 KB Output is correct
12 Runtime error 5 ms 4596 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6320 KB Output is correct
2 Correct 34 ms 6332 KB Output is correct
3 Correct 34 ms 6380 KB Output is correct
4 Correct 20 ms 4764 KB Output is correct
5 Correct 19 ms 5676 KB Output is correct
6 Correct 18 ms 5292 KB Output is correct
7 Correct 18 ms 5284 KB Output is correct
8 Correct 18 ms 5428 KB Output is correct
9 Correct 18 ms 5428 KB Output is correct
10 Correct 16 ms 4712 KB Output is correct
11 Correct 17 ms 4888 KB Output is correct
12 Correct 16 ms 4584 KB Output is correct
13 Correct 19 ms 4584 KB Output is correct
14 Correct 17 ms 4772 KB Output is correct
15 Correct 18 ms 5040 KB Output is correct
16 Correct 18 ms 5048 KB Output is correct
17 Correct 18 ms 4904 KB Output is correct
18 Correct 20 ms 4996 KB Output is correct
19 Correct 23 ms 4908 KB Output is correct
20 Correct 17 ms 5424 KB Output is correct
21 Correct 14 ms 5420 KB Output is correct
22 Correct 17 ms 5228 KB Output is correct
23 Correct 18 ms 5292 KB Output is correct
24 Correct 18 ms 5164 KB Output is correct
25 Correct 18 ms 5276 KB Output is correct
26 Correct 20 ms 5272 KB Output is correct
27 Correct 20 ms 5216 KB Output is correct
28 Correct 18 ms 5284 KB Output is correct
29 Correct 16 ms 5096 KB Output is correct
30 Correct 17 ms 5156 KB Output is correct
31 Correct 3 ms 3056 KB Output is correct
32 Correct 3 ms 3048 KB Output is correct
33 Correct 4 ms 3052 KB Output is correct
34 Correct 4 ms 3048 KB Output is correct
35 Runtime error 4 ms 4584 KB Execution killed with signal 6
36 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 2 ms 3048 KB Output is correct
4 Runtime error 6 ms 5252 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
50.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6228 KB Output is correct
2 Partially correct 30 ms 6308 KB Partially correct
3 Correct 28 ms 6360 KB Output is correct
4 Correct 18 ms 4784 KB Output is correct
5 Correct 22 ms 5912 KB Output is correct
6 Correct 20 ms 5368 KB Output is correct
7 Correct 24 ms 5348 KB Output is correct
8 Correct 19 ms 5168 KB Output is correct
9 Correct 18 ms 5256 KB Output is correct
10 Correct 16 ms 4780 KB Output is correct
11 Correct 17 ms 4780 KB Output is correct
12 Correct 16 ms 4632 KB Output is correct
13 Correct 17 ms 4680 KB Output is correct
14 Correct 17 ms 4772 KB Output is correct
15 Correct 18 ms 5004 KB Output is correct
16 Correct 18 ms 4956 KB Output is correct
17 Correct 20 ms 4908 KB Output is correct
18 Correct 20 ms 4876 KB Output is correct
19 Correct 17 ms 4908 KB Output is correct
20 Correct 19 ms 5420 KB Output is correct
21 Correct 16 ms 5348 KB Output is correct
22 Correct 18 ms 5272 KB Output is correct
23 Correct 17 ms 5208 KB Output is correct
24 Correct 18 ms 5216 KB Output is correct
25 Correct 18 ms 5300 KB Output is correct
26 Correct 18 ms 5296 KB Output is correct
27 Correct 18 ms 5420 KB Output is correct
28 Correct 18 ms 5164 KB Output is correct
29 Correct 18 ms 4900 KB Output is correct
30 Correct 20 ms 5104 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6416 KB Output is correct
2 Correct 30 ms 6216 KB Output is correct
3 Correct 28 ms 6304 KB Output is correct
4 Incorrect 17 ms 4936 KB Output isn't correct
5 Halted 0 ms 0 KB -