oj.uz

Submission #257819

# Submission time Handle Problem Language Result Execution time Memory
257819 2020-08-04T20:55:18 Z Blagojce Amusement Park (JOI17_amusement_park) C++17
80 / 100
 40 ms 9492 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
 
#include "Joi.h"
/*int VAL[mxn];
void MessageBoard(int u, int val){
	VAL[u] = val;
	return;
}*/
 
int n, m;
int a[mxn], b[mxn];
bool vis[mxn];
vector<int> g[mxn];
 
int itopos[mxn];
int temp_p = 0;
 
int depth[mxn];

void dfs(int u){
	itopos[u] = temp_p++;
	vis[u] = true;
	for(auto e : g[u]){
		if(vis[e]) continue;
		depth[e] = depth[u] + 1;
		dfs(e);
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N, m = M;
	fr(i, 0, m) a[i] = A[i], b[i] = B[i];
	fr(i, 0, m){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	dfs(0);
	int mxd = 0;
	fr(i, 0, n) mxd = max(mxd, depth[i]);
	if(mxd < 59){
		fr(i, 0, n){
			if(X&(1LL<<(itopos[i]%60))) MessageBoard(i,1); 
			else MessageBoard(i,0);
		}
	}
	else{
		fr(i, 0, n){
			if(X&(1LL<<(depth[i]%60)))MessageBoard(i,1); 
			else MessageBoard(i,0);
		}
	}
	
}

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
#include "Ioi.h"
/*
int mark[60] = {1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int Move(int u){
	cout<<u<<endl;
	return mark[u];
}*/

int n, m;
int a[mxn], b[mxn];
bool vis[mxn];
vector<int> g[mxn];

int postoi[mxn];
int temp_p = 0;

vector<int> v;

int val[mxn];
int parent[mxn];
int depth[mxn];
int mx_depth[mxn];

int best_child[mxn];

void dfs(int u, int p){
	parent[u] = p;
	postoi[temp_p] = u;
	++temp_p;
	
	vis[u] = true;
	mx_depth[u] = depth[u];
	best_child[u] = u;
	for(auto e : g[u]){
		if(vis[e]) continue;		
		depth[e] = depth[u] + 1;
		dfs(e, u);
		if(mx_depth[e] > mx_depth[u]){
			mx_depth[u] = mx_depth[e];
			best_child[u] = e;
		}
	
	}
}

int loc_pos;
void dfs2(int u, int p, int tv){
	loc_pos ++;
	val[u] = tv;
	vis[u] = true;
	if(loc_pos == 60) return;
	
	for(auto e : g[u]){
		if(vis[e]) continue;
		dfs2(e, u, Move(e));
		if(loc_pos == 60) return;
	}
	
	if(u != p) Move(parent[u]);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n = N, m = M;
	fr(i, 0, m) a[i] = A[i], b[i] = B[i];
	fr(i, 0, m){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	dfs(0, 0);
	
	if(mx_depth[0] < 59){	
		while(P != 0) V = Move(parent[P]), P = parent[P];
		val[0] = V;
		
		memset(vis, false, sizeof(vis));
		dfs2(0, 0, V);
		
		ll X = 0;
		fr(i, 0, 60){
			X |= (1LL<<i)*val[postoi[i]];
		}
		return X;
	}
	else{
		while(depth[P]%60 != 0) V = Move(parent[P]), P = parent[P];
		ll X = 0;
		if(mx_depth[P]-depth[P]<59){
			fr(i, 0, 60){
				V = Move(parent[P]);
				P = parent[P];
				X  |= (1LL<<(59-i))*V;
			}
		}
		else{
			X |= (1LL << 0)*V;
			fr(i, 1, 60){
				V = Move(best_child[P]);
				P = best_child[P];
				X |= (1LL<<i)*V;
			}
		}
		return X;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5508 KB Output is correct
2 Correct 4 ms 5636 KB Output is correct
3 Correct 4 ms 5672 KB Output is correct
4 Correct 5 ms 5548 KB Output is correct
5 Correct 4 ms 5508 KB Output is correct
6 Correct 4 ms 5664 KB Output is correct
7 Correct 4 ms 5644 KB Output is correct
8 Correct 4 ms 5664 KB Output is correct
9 Correct 4 ms 5644 KB Output is correct
10 Correct 5 ms 5680 KB Output is correct
11 Correct 7 ms 5944 KB Output is correct
12 Correct 4 ms 5672 KB Output is correct
13 Correct 4 ms 5644 KB Output is correct
14 Correct 4 ms 5668 KB Output is correct
15 Correct 4 ms 5516 KB Output is correct
16 Correct 4 ms 5664 KB Output is correct
17 Correct 4 ms 5660 KB Output is correct
18 Correct 4 ms 5648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9160 KB Output is correct
2 Correct 35 ms 9104 KB Output is correct
3 Correct 35 ms 9100 KB Output is correct
4 Correct 19 ms 7708 KB Output is correct
5 Correct 19 ms 8096 KB Output is correct
6 Correct 20 ms 7840 KB Output is correct
7 Correct 22 ms 7744 KB Output is correct
8 Correct 19 ms 7968 KB Output is correct
9 Correct 19 ms 7968 KB Output is correct
10 Correct 18 ms 7716 KB Output is correct
11 Correct 22 ms 7708 KB Output is correct
12 Correct 19 ms 7488 KB Output is correct
13 Correct 18 ms 7624 KB Output is correct
14 Correct 20 ms 7664 KB Output is correct
15 Correct 19 ms 7712 KB Output is correct
16 Correct 23 ms 7744 KB Output is correct
17 Correct 23 ms 7948 KB Output is correct
18 Correct 24 ms 7768 KB Output is correct
19 Correct 20 ms 7840 KB Output is correct
20 Correct 19 ms 7908 KB Output is correct
21 Correct 17 ms 8096 KB Output is correct
22 Correct 18 ms 7712 KB Output is correct
23 Correct 20 ms 7712 KB Output is correct
24 Correct 26 ms 7852 KB Output is correct
25 Correct 19 ms 7840 KB Output is correct
26 Correct 19 ms 8100 KB Output is correct
27 Correct 24 ms 7972 KB Output is correct
28 Correct 20 ms 7968 KB Output is correct
29 Correct 19 ms 7908 KB Output is correct
30 Correct 19 ms 7828 KB Output is correct
31 Correct 4 ms 5512 KB Output is correct
32 Correct 4 ms 5668 KB Output is correct
33 Correct 5 ms 5660 KB Output is correct
34 Correct 4 ms 5664 KB Output is correct
35 Correct 5 ms 5672 KB Output is correct
36 Correct 4 ms 5512 KB Output is correct
37 Correct 4 ms 5676 KB Output is correct
38 Correct 6 ms 5680 KB Output is correct
39 Correct 5 ms 5640 KB Output is correct
40 Correct 4 ms 5512 KB Output is correct
41 Correct 4 ms 5512 KB Output is correct
42 Correct 4 ms 5512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5548 KB Output is correct
2 Correct 5 ms 5512 KB Output is correct
3 Correct 4 ms 5512 KB Output is correct
4 Correct 7 ms 6168 KB Output is correct
5 Correct 6 ms 5940 KB Output is correct
6 Correct 6 ms 6168 KB Output is correct
7 Correct 6 ms 5940 KB Output is correct
8 Correct 6 ms 6168 KB Output is correct
9 Correct 18 ms 8492 KB Output is correct
10 Correct 17 ms 8576 KB Output is correct
11 Correct 17 ms 8364 KB Output is correct
12 Correct 4 ms 5512 KB Output is correct
13 Correct 4 ms 5512 KB Output is correct
14 Correct 4 ms 5564 KB Output is correct
15 Correct 4 ms 5512 KB Output is correct

Subtask #4
52.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9032 KB Output is correct
2 Correct 36 ms 9492 KB Output is correct
3 Correct 33 ms 9472 KB Output is correct
4 Correct 23 ms 7852 KB Output is correct
5 Correct 20 ms 8252 KB Output is correct
6 Correct 24 ms 8136 KB Output is correct
7 Correct 19 ms 8088 KB Output is correct
8 Correct 20 ms 7740 KB Output is correct
9 Correct 20 ms 7996 KB Output is correct
10 Correct 17 ms 7872 KB Output is correct
11 Correct 19 ms 7936 KB Output is correct
12 Correct 19 ms 7644 KB Output is correct
13 Partially correct 19 ms 7764 KB Partially correct
14 Partially correct 18 ms 7600 KB Partially correct
15 Correct 19 ms 7740 KB Output is correct
16 Correct 20 ms 7740 KB Output is correct
17 Correct 18 ms 7956 KB Output is correct
18 Partially correct 19 ms 7740 KB Partially correct
19 Partially correct 19 ms 7740 KB Partially correct
20 Correct 15 ms 7996 KB Output is correct
21 Correct 15 ms 7996 KB Output is correct
22 Correct 19 ms 8096 KB Output is correct
23 Correct 19 ms 8120 KB Output is correct
24 Correct 20 ms 8120 KB Output is correct
25 Correct 19 ms 8088 KB Output is correct
26 Correct 19 ms 8104 KB Output is correct
27 Correct 19 ms 7996 KB Output is correct
28 Correct 23 ms 7880 KB Output is correct
29 Correct 19 ms 7716 KB Output is correct
30 Correct 20 ms 7888 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9236 KB Output is correct
2 Correct 37 ms 9492 KB Output is correct
3 Correct 40 ms 9324 KB Output is correct
4 Correct 23 ms 7940 KB Output is correct
5 Correct 20 ms 8380 KB Output is correct
6 Correct 26 ms 7996 KB Output is correct
7 Correct 20 ms 7996 KB Output is correct
8 Correct 23 ms 8088 KB Output is correct
9 Correct 23 ms 7868 KB Output is correct
10 Correct 17 ms 7912 KB Output is correct
11 Correct 17 ms 7744 KB Output is correct
12 Correct 17 ms 7624 KB Output is correct
13 Incorrect 18 ms 7460 KB Output isn't correct
14 Halted 0 ms 0 KB -