oj.uz

Submission #676889

# Submission time Handle Problem Language Result Execution time Memory
676889 2023-01-01T13:13:55 Z radal Amusement Park (JOI17_amusement_park) C++17
77 / 100
 48 ms 50408 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;
	while (cur){
		int p = par[cur];
		int i = 0;
		while (adj[p][i] != cur) i++;
		rotate(adj[p].begin(),adj[p].begin()+i,adj[p].end());
		cur = p;
	}
	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;
			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 24 ms 47732 KB Output is correct
2 Correct 25 ms 47644 KB Output is correct
3 Correct 24 ms 47668 KB Output is correct
4 Correct 25 ms 47620 KB Output is correct
5 Correct 26 ms 47732 KB Output is correct
6 Correct 24 ms 47664 KB Output is correct
7 Correct 25 ms 47688 KB Output is correct
8 Correct 25 ms 47672 KB Output is correct
9 Correct 26 ms 47672 KB Output is correct
10 Correct 25 ms 47664 KB Output is correct
11 Correct 30 ms 48000 KB Output is correct
12 Correct 24 ms 47564 KB Output is correct
13 Correct 24 ms 47676 KB Output is correct
14 Correct 26 ms 47684 KB Output is correct
15 Correct 25 ms 47668 KB Output is correct
16 Correct 27 ms 47668 KB Output is correct
17 Correct 24 ms 47668 KB Output is correct
18 Correct 26 ms 47652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 50280 KB Output is correct
2 Correct 45 ms 50248 KB Output is correct
3 Correct 48 ms 50408 KB Output is correct
4 Correct 36 ms 49260 KB Output is correct
5 Correct 38 ms 49440 KB Output is correct
6 Correct 38 ms 49356 KB Output is correct
7 Correct 39 ms 49380 KB Output is correct
8 Correct 35 ms 49296 KB Output is correct
9 Correct 37 ms 49396 KB Output is correct
10 Correct 37 ms 49280 KB Output is correct
11 Correct 38 ms 49220 KB Output is correct
12 Correct 35 ms 49124 KB Output is correct
13 Correct 36 ms 49168 KB Output is correct
14 Correct 36 ms 49212 KB Output is correct
15 Correct 36 ms 49224 KB Output is correct
16 Correct 36 ms 49232 KB Output is correct
17 Correct 36 ms 49144 KB Output is correct
18 Correct 41 ms 49152 KB Output is correct
19 Correct 36 ms 49172 KB Output is correct
20 Correct 37 ms 49528 KB Output is correct
21 Correct 33 ms 49520 KB Output is correct
22 Correct 38 ms 49356 KB Output is correct
23 Correct 41 ms 49380 KB Output is correct
24 Correct 37 ms 49428 KB Output is correct
25 Correct 37 ms 49312 KB Output is correct
26 Correct 37 ms 49400 KB Output is correct
27 Correct 37 ms 49272 KB Output is correct
28 Correct 35 ms 49576 KB Output is correct
29 Correct 34 ms 49208 KB Output is correct
30 Correct 36 ms 49428 KB Output is correct
31 Correct 25 ms 47664 KB Output is correct
32 Correct 27 ms 47724 KB Output is correct
33 Correct 25 ms 47616 KB Output is correct
34 Correct 26 ms 47548 KB Output is correct
35 Correct 27 ms 47736 KB Output is correct
36 Correct 25 ms 47724 KB Output is correct
37 Correct 25 ms 47660 KB Output is correct
38 Correct 23 ms 47664 KB Output is correct
39 Correct 25 ms 47700 KB Output is correct
40 Correct 25 ms 47688 KB Output is correct
41 Correct 24 ms 47644 KB Output is correct
42 Correct 24 ms 47592 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47780 KB Output is correct
2 Correct 26 ms 47644 KB Output is correct
3 Correct 24 ms 47656 KB Output is correct
4 Correct 26 ms 47960 KB Output is correct
5 Correct 27 ms 47948 KB Output is correct
6 Correct 27 ms 47972 KB Output is correct
7 Correct 27 ms 47948 KB Output is correct
8 Correct 26 ms 48060 KB Output is correct
9 Correct 33 ms 49568 KB Output is correct
10 Correct 33 ms 49592 KB Output is correct
11 Correct 35 ms 49732 KB Output is correct
12 Correct 24 ms 47620 KB Output is correct
13 Correct 27 ms 47624 KB Output is correct
14 Correct 28 ms 47672 KB Output is correct
15 Correct 30 ms 47720 KB Output is correct

Subtask #4
49.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50332 KB Output is correct
2 Correct 43 ms 50372 KB Output is correct
3 Correct 45 ms 50240 KB Output is correct
4 Correct 38 ms 49168 KB Output is correct
5 Partially correct 40 ms 49672 KB Partially correct
6 Correct 36 ms 49548 KB Output is correct
7 Correct 35 ms 49464 KB Output is correct
8 Correct 38 ms 49272 KB Output is correct
9 Correct 37 ms 49300 KB Output is correct
10 Correct 34 ms 49272 KB Output is correct
11 Correct 35 ms 49252 KB Output is correct
12 Correct 35 ms 49040 KB Output is correct
13 Correct 35 ms 49016 KB Output is correct
14 Correct 35 ms 49348 KB Output is correct
15 Correct 36 ms 49172 KB Output is correct
16 Correct 40 ms 49168 KB Output is correct
17 Correct 36 ms 49380 KB Output is correct
18 Correct 35 ms 49256 KB Output is correct
19 Partially correct 39 ms 49144 KB Partially correct
20 Correct 35 ms 49516 KB Output is correct
21 Correct 34 ms 49324 KB Output is correct
22 Correct 37 ms 49436 KB Output is correct
23 Correct 36 ms 49376 KB Output is correct
24 Correct 35 ms 49264 KB Output is correct
25 Correct 36 ms 49364 KB Output is correct
26 Correct 38 ms 49460 KB Output is correct
27 Correct 40 ms 49328 KB Output is correct
28 Correct 43 ms 49464 KB Output is correct
29 Correct 35 ms 49384 KB Output is correct
30 Correct 36 ms 49328 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 50348 KB Output is correct
2 Correct 45 ms 50380 KB Output is correct
3 Correct 48 ms 50408 KB Output is correct
4 Incorrect 37 ms 49220 KB Output isn't correct
5 Halted 0 ms 0 KB -