oj.uz

Submission #676884

# Submission time Handle Problem Language Result Execution time Memory
676884 2023-01-01T13:05:16 Z radal Amusement Park (JOI17_amusement_park) C++17
73 / 100
 53 ms 50428 KB 
#include <bits/stdc++.h>
#include "Joi.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;

vector<int> aadj[N];
int TT,ttin[N];
bool vvis[N];

void dfs(int v,ll x){
	if ((x&(1ll << (TT%60)))) MessageBoard(v,1);
	else MessageBoard(v,0);
	ttin[v] = TT++;
	vvis[v] = 1;
	for (int u : aadj[v]) if (!vvis[u]) dfs(u,x);
}

void Joi(int n, int m, int A[], int B[], long long x, int tt) {
	rep(i,0,m){
		aadj[A[i]].pb(B[i]);
		aadj[B[i]].pb(A[i]);
	}
	rep(i,0,n) sort(all(aadj[i]));
	dfs(0,x);
	return;
}

#include "Ioi.h"
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;
constexpr ll inf = 1e9+10;

vector<int> adj[N];
bool vis[N];
int tin[N],T;
int par[N],ans[70];
int po[N],h[N];

void dfs(int v){
	vis[v] = 1;
	tin[v] = T++;
	for (int u : adj[v]) if (!vis[u]){
		h[u] = h[v]+1;
		par[u] = v;
	   	dfs(u);
	}
}

long long Ioi(int n, int m, int A[], int B[], int P, int v, int tt) {
	rep(i,0,m){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	rep(i,0,n) sort(all(adj[i]));
	dfs(0);
	memset(ans,-1,sizeof ans);
	swap(P,v);
	int cur = v;
	ans[tin[cur]%60] = P;
	int cnt = 1;
	while (cnt < 60){
		int fl = -1;
		int sz = adj[cur].size();
		while (po[cur] < sz){
			int u = adj[cur][po[cur]];
			po[cur]++;
			if (par[u] != cur) continue;
			if (ans[tin[u]%60] != -1) continue;
			fl = u;		
			break;
		}
		if (fl == -1)
			fl = par[cur];
		int t = tin[fl]%60;
		if (ans[t] == -1) cnt++;
		ans[t] = Move(fl);
		cur = fl;
	}
	ll out = 0;
	rep(i,0,60) if (ans[i]) out += (1ll << i);
	return out;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47656 KB Output is correct
2 Correct 27 ms 47860 KB Output is correct
3 Correct 26 ms 47688 KB Output is correct
4 Correct 24 ms 47692 KB Output is correct
5 Correct 25 ms 47668 KB Output is correct
6 Correct 26 ms 47716 KB Output is correct
7 Correct 25 ms 47696 KB Output is correct
8 Correct 24 ms 47692 KB Output is correct
9 Correct 25 ms 47684 KB Output is correct
10 Correct 24 ms 47536 KB Output is correct
11 Correct 28 ms 48020 KB Output is correct
12 Correct 24 ms 47672 KB Output is correct
13 Correct 24 ms 47704 KB Output is correct
14 Correct 27 ms 47696 KB Output is correct
15 Correct 25 ms 47676 KB Output is correct
16 Correct 25 ms 47660 KB Output is correct
17 Correct 26 ms 47720 KB Output is correct
18 Correct 25 ms 47676 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50284 KB Output is correct
2 Correct 45 ms 50312 KB Output is correct
3 Correct 46 ms 50236 KB Output is correct
4 Correct 37 ms 49144 KB Output is correct
5 Correct 37 ms 49576 KB Output is correct
6 Correct 36 ms 49492 KB Output is correct
7 Correct 39 ms 49572 KB Output is correct
8 Correct 38 ms 49536 KB Output is correct
9 Correct 36 ms 49620 KB Output is correct
10 Correct 36 ms 49628 KB Output is correct
11 Correct 35 ms 49520 KB Output is correct
12 Correct 35 ms 49212 KB Output is correct
13 Correct 37 ms 49344 KB Output is correct
14 Correct 36 ms 49408 KB Output is correct
15 Correct 35 ms 49572 KB Output is correct
16 Correct 35 ms 49392 KB Output is correct
17 Correct 37 ms 49444 KB Output is correct
18 Correct 37 ms 49532 KB Output is correct
19 Correct 36 ms 49500 KB Output is correct
20 Correct 34 ms 49708 KB Output is correct
21 Correct 33 ms 49620 KB Output is correct
22 Correct 38 ms 49512 KB Output is correct
23 Correct 37 ms 49712 KB Output is correct
24 Correct 37 ms 49604 KB Output is correct
25 Correct 36 ms 49648 KB Output is correct
26 Correct 37 ms 49668 KB Output is correct
27 Correct 40 ms 49532 KB Output is correct
28 Correct 36 ms 49612 KB Output is correct
29 Correct 37 ms 49460 KB Output is correct
30 Correct 36 ms 49500 KB Output is correct
31 Correct 24 ms 47648 KB Output is correct
32 Correct 26 ms 47672 KB Output is correct
33 Correct 24 ms 47700 KB Output is correct
34 Correct 25 ms 47692 KB Output is correct
35 Incorrect 24 ms 47648 KB Wrong Answer [7]
36 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47640 KB Output is correct
2 Correct 24 ms 47664 KB Output is correct
3 Correct 25 ms 47748 KB Output is correct
4 Correct 25 ms 47948 KB Output is correct
5 Correct 24 ms 47956 KB Output is correct
6 Correct 25 ms 47980 KB Output is correct
7 Correct 24 ms 47996 KB Output is correct
8 Correct 25 ms 48012 KB Output is correct
9 Correct 35 ms 49576 KB Output is correct
10 Correct 40 ms 49572 KB Output is correct
11 Correct 35 ms 49612 KB Output is correct
12 Correct 25 ms 47656 KB Output is correct
13 Correct 25 ms 47664 KB Output is correct
14 Correct 27 ms 47700 KB Output is correct
15 Correct 25 ms 47648 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 50260 KB Output is correct
2 Correct 53 ms 50428 KB Output is correct
3 Correct 45 ms 50420 KB Output is correct
4 Correct 37 ms 49196 KB Output is correct
5 Correct 36 ms 49752 KB Output is correct
6 Correct 38 ms 49512 KB Output is correct
7 Correct 35 ms 49664 KB Output is correct
8 Correct 35 ms 49504 KB Output is correct
9 Correct 37 ms 49596 KB Output is correct
10 Correct 37 ms 49612 KB Output is correct
11 Correct 35 ms 49616 KB Output is correct
12 Correct 39 ms 49240 KB Output is correct
13 Correct 37 ms 49312 KB Output is correct
14 Correct 36 ms 49432 KB Output is correct
15 Correct 36 ms 49492 KB Output is correct
16 Correct 35 ms 49392 KB Output is correct
17 Correct 37 ms 49488 KB Output is correct
18 Correct 35 ms 49464 KB Output is correct
19 Correct 36 ms 49416 KB Output is correct
20 Correct 34 ms 49612 KB Output is correct
21 Correct 32 ms 49616 KB Output is correct
22 Correct 36 ms 49636 KB Output is correct
23 Correct 38 ms 49592 KB Output is correct
24 Correct 36 ms 49672 KB Output is correct
25 Correct 37 ms 49644 KB Output is correct
26 Correct 37 ms 49580 KB Output is correct
27 Correct 36 ms 49604 KB Output is correct
28 Correct 37 ms 49628 KB Output is correct
29 Correct 34 ms 49480 KB Output is correct
30 Correct 35 ms 49532 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 50308 KB Output is correct
2 Correct 44 ms 50364 KB Output is correct
3 Correct 44 ms 50412 KB Output is correct
4 Correct 36 ms 49224 KB Output is correct
5 Correct 39 ms 49768 KB Output is correct
6 Correct 37 ms 49728 KB Output is correct
7 Correct 38 ms 49540 KB Output is correct
8 Correct 38 ms 49676 KB Output is correct
9 Correct 36 ms 49660 KB Output is correct
10 Correct 35 ms 49600 KB Output is correct
11 Correct 37 ms 49656 KB Output is correct
12 Correct 36 ms 49364 KB Output is correct
13 Correct 35 ms 49304 KB Output is correct
14 Correct 35 ms 49368 KB Output is correct
15 Correct 37 ms 49588 KB Output is correct
16 Correct 35 ms 49472 KB Output is correct
17 Correct 37 ms 49380 KB Output is correct
18 Correct 35 ms 49492 KB Output is correct
19 Correct 37 ms 49508 KB Output is correct
20 Correct 32 ms 49620 KB Output is correct
21 Correct 33 ms 49600 KB Output is correct
22 Correct 36 ms 49732 KB Output is correct
23 Correct 37 ms 49608 KB Output is correct
24 Correct 36 ms 49616 KB Output is correct
25 Correct 36 ms 49592 KB Output is correct
26 Correct 36 ms 49656 KB Output is correct
27 Correct 35 ms 49648 KB Output is correct
28 Correct 40 ms 49540 KB Output is correct
29 Correct 37 ms 49432 KB Output is correct
30 Correct 40 ms 49416 KB Output is correct
31 Correct 22 ms 47760 KB Output is correct
32 Correct 23 ms 47676 KB Output is correct
33 Correct 24 ms 47664 KB Output is correct
34 Correct 24 ms 47656 KB Output is correct
35 Correct 25 ms 47712 KB Output is correct
36 Correct 28 ms 47788 KB Output is correct
37 Correct 26 ms 47696 KB Output is correct
38 Correct 24 ms 47592 KB Output is correct
39 Correct 24 ms 47672 KB Output is correct
40 Incorrect 25 ms 47668 KB Wrong Answer [7]
41 Halted 0 ms 0 KB -