oj.uz

Submission #51786

# Submission time Handle Problem Language Result Execution time Memory
51786 2018-06-21T07:33:20 Z ainta Amusement Park (JOI17_amusement_park) C++17
100 / 100
 43 ms 24416 KB 
#include "Joi.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 10100
using namespace std;

struct TTT {
	vector<int>E[N_];
	vector<int>G[N_];
	int Dep[N_], D[N_], C[N_], v[N_], par[N_];
	long long c = 0;
	struct point {
		int a, d;
		bool operator <(const point &p)const {
			return d > p.d;
		}
	};
	void DFS(int a, int pp) {
		C[a] = 1;
		D[a] = 1;
		v[a] = 1;
		vector<point>V;
		for (auto &x : E[a]) {
			if (v[x])continue;
			Dep[x] = Dep[a] + 1;
			DFS(x, a);
			D[a] = max(D[a], D[x] + 1);
			C[a] += C[x];
			par[x] = a;
			V.push_back({ x,D[x] });
		}
		if (!V.empty()) {
			sort(V.begin(), V.end());
			for (auto &x : V) {
				G[a].push_back(x.a);
			}
		}
	}
	int cnt = 0;
	long long xx;
	void Go(int a) {
		MessageBoard(a, (xx >> (cnt % 60)) & 1);
		cnt++;
		for (auto &x : G[a]) {
			Go(x);
		}
	}

}TT;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	TT.xx = X;
	int i;
	for (i = 0; i < M; i++) {
		TT.E[A[i]].push_back(B[i]);
		TT.E[B[i]].push_back(A[i]);
	}
	TT.DFS(0, -1);
	TT.Go(0);
}

#include "Ioi.h"

#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 10100
using namespace std;

vector<int>E[N_];
vector<int>G[N_];
int Dep[N_], D[N_], C[N_], par[N_], v[N_];
long long c = 0;
struct point {
	int a, d;
	bool operator <(const point &p)const {
		return d > p.d;
	}
};
void DFS(int a, int pp) {
	C[a] = 1;
	D[a] = 1;
	v[a] = 1;
	vector<point>V;
	for (auto &x : E[a]) {
		if (v[x])continue;
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
		D[a] = max(D[a], D[x] + 1);
		C[a] += C[x];
		par[x] = a;
		V.push_back({ x,D[x] });
	}
	if (!V.empty()) {
		sort(V.begin(), V.end());
		for (auto &x : V) {
			G[a].push_back(x.a);
		}
	}
}
int cnt = 0, U[N_], Num[N_], Ed[N_], ReNum[N_];
long long xx;
void Go(int a) {
	U[a] = cnt % 60;
	cnt++;
	Num[a] = cnt;
	ReNum[cnt] = a;
	for (auto &x : G[a]) {
		Go(x);
	}
	Ed[a] = cnt;
}
int pv;
long long res;
void Add(int a, int x) {
	res += (1ll << U[a])*x;
}
void Calc(int a, int pp) {
	int ck = 0;
	if (a == pv)return;
	for (auto &x : G[a]) {
		if (Num[x] > 60)continue;
		if (Num[x] <= Num[pv] && Num[pv] <= Ed[x])continue;
		Add(x, Move(x));
		Calc(x, a);
	}
	for (auto &x : G[a]) {
		if (Num[x] <= Num[pv] && Num[pv] <= Ed[x]) {
			Add(x, Move(x));
			Calc(x, a);
			return;
		}
	}
	if (pp == -1) {
		while (1) {}
	}
	Move(pp);
	return;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	int i;
	for (i = 0; i < M; i++) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(0, -1);
	Go(0);
	int a = P;
	while (a != 0 && D[a] < 60) {
		V = Move(par[a]);
		a = par[a];
	}
	Add(a, V);
	if (D[a] >= 60) {
		for (i = 0; i < 59; i++) {
			V = Move(G[a][0]);
			a = G[a][0];
			Add(a, V);
		}
		return res;
	}
	for (i = 1; i <= 60; i++) {
		if (Dep[ReNum[i]] == D[0]-1)pv = ReNum[i];
	}
	Calc(a,-1);
	return res;
}

Compilation message

Ioi.cpp: In function 'void Calc(int, int)':
Ioi.cpp:58:6: warning: unused variable 'ck' [-Wunused-variable]
  int ck = 0;
      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1632 KB Output is correct
2 Correct 5 ms 1924 KB Output is correct
3 Correct 5 ms 2004 KB Output is correct
4 Correct 4 ms 2032 KB Output is correct
5 Correct 5 ms 2212 KB Output is correct
6 Correct 4 ms 2272 KB Output is correct
7 Correct 6 ms 2292 KB Output is correct
8 Correct 8 ms 2328 KB Output is correct
9 Correct 5 ms 2488 KB Output is correct
10 Correct 7 ms 2636 KB Output is correct
11 Correct 10 ms 2676 KB Output is correct
12 Correct 4 ms 2696 KB Output is correct
13 Correct 6 ms 2696 KB Output is correct
14 Correct 5 ms 2696 KB Output is correct
15 Correct 5 ms 2696 KB Output is correct
16 Correct 5 ms 2696 KB Output is correct
17 Correct 5 ms 2696 KB Output is correct
18 Correct 6 ms 2696 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6476 KB Output is correct
2 Correct 43 ms 6868 KB Output is correct
3 Correct 41 ms 7332 KB Output is correct
4 Correct 30 ms 7496 KB Output is correct
5 Correct 25 ms 7496 KB Output is correct
6 Correct 26 ms 7496 KB Output is correct
7 Correct 28 ms 7496 KB Output is correct
8 Correct 36 ms 7496 KB Output is correct
9 Correct 29 ms 7536 KB Output is correct
10 Correct 20 ms 7576 KB Output is correct
11 Correct 22 ms 7576 KB Output is correct
12 Correct 27 ms 7576 KB Output is correct
13 Correct 26 ms 7576 KB Output is correct
14 Correct 23 ms 7704 KB Output is correct
15 Correct 33 ms 7972 KB Output is correct
16 Correct 24 ms 8208 KB Output is correct
17 Correct 26 ms 8304 KB Output is correct
18 Correct 40 ms 8380 KB Output is correct
19 Correct 24 ms 8540 KB Output is correct
20 Correct 28 ms 9804 KB Output is correct
21 Correct 23 ms 10088 KB Output is correct
22 Correct 25 ms 10088 KB Output is correct
23 Correct 39 ms 10124 KB Output is correct
24 Correct 39 ms 10160 KB Output is correct
25 Correct 27 ms 10356 KB Output is correct
26 Correct 26 ms 10728 KB Output is correct
27 Correct 25 ms 10916 KB Output is correct
28 Correct 35 ms 11092 KB Output is correct
29 Correct 26 ms 11256 KB Output is correct
30 Correct 33 ms 11288 KB Output is correct
31 Correct 7 ms 11320 KB Output is correct
32 Correct 6 ms 11320 KB Output is correct
33 Correct 6 ms 11320 KB Output is correct
34 Correct 6 ms 11320 KB Output is correct
35 Correct 6 ms 11320 KB Output is correct
36 Correct 5 ms 11320 KB Output is correct
37 Correct 6 ms 11320 KB Output is correct
38 Correct 5 ms 11320 KB Output is correct
39 Correct 6 ms 11320 KB Output is correct
40 Correct 6 ms 11320 KB Output is correct
41 Correct 6 ms 11320 KB Output is correct
42 Correct 4 ms 11320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11320 KB Output is correct
2 Correct 5 ms 11320 KB Output is correct
3 Correct 6 ms 11320 KB Output is correct
4 Correct 8 ms 11320 KB Output is correct
5 Correct 8 ms 11320 KB Output is correct
6 Correct 8 ms 11320 KB Output is correct
7 Correct 9 ms 11320 KB Output is correct
8 Correct 8 ms 11320 KB Output is correct
9 Correct 28 ms 13144 KB Output is correct
10 Correct 22 ms 13568 KB Output is correct
11 Correct 22 ms 13820 KB Output is correct
12 Correct 7 ms 13864 KB Output is correct
13 Correct 5 ms 13864 KB Output is correct
14 Correct 6 ms 13864 KB Output is correct
15 Correct 5 ms 13864 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13864 KB Output is correct
2 Correct 40 ms 13952 KB Output is correct
3 Correct 38 ms 14272 KB Output is correct
4 Correct 27 ms 14504 KB Output is correct
5 Correct 28 ms 14504 KB Output is correct
6 Correct 26 ms 14504 KB Output is correct
7 Correct 35 ms 14504 KB Output is correct
8 Correct 32 ms 14504 KB Output is correct
9 Correct 33 ms 14504 KB Output is correct
10 Correct 22 ms 14504 KB Output is correct
11 Correct 24 ms 14504 KB Output is correct
12 Correct 23 ms 14504 KB Output is correct
13 Correct 22 ms 14504 KB Output is correct
14 Correct 24 ms 14504 KB Output is correct
15 Correct 24 ms 14796 KB Output is correct
16 Correct 23 ms 15000 KB Output is correct
17 Correct 24 ms 15096 KB Output is correct
18 Correct 24 ms 15172 KB Output is correct
19 Correct 29 ms 15348 KB Output is correct
20 Correct 20 ms 16472 KB Output is correct
21 Correct 22 ms 16740 KB Output is correct
22 Correct 24 ms 16848 KB Output is correct
23 Correct 25 ms 16900 KB Output is correct
24 Correct 24 ms 16952 KB Output is correct
25 Correct 27 ms 17132 KB Output is correct
26 Correct 25 ms 17620 KB Output is correct
27 Correct 25 ms 17992 KB Output is correct
28 Correct 25 ms 17992 KB Output is correct
29 Correct 23 ms 17992 KB Output is correct
30 Correct 23 ms 18252 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 19368 KB Output is correct
2 Correct 40 ms 19756 KB Output is correct
3 Correct 41 ms 20180 KB Output is correct
4 Correct 24 ms 20408 KB Output is correct
5 Correct 24 ms 20536 KB Output is correct
6 Correct 25 ms 20664 KB Output is correct
7 Correct 23 ms 20664 KB Output is correct
8 Correct 32 ms 20664 KB Output is correct
9 Correct 32 ms 20664 KB Output is correct
10 Correct 20 ms 20664 KB Output is correct
11 Correct 20 ms 20664 KB Output is correct
12 Correct 23 ms 20664 KB Output is correct
13 Correct 23 ms 20664 KB Output is correct
14 Correct 23 ms 20664 KB Output is correct
15 Correct 25 ms 20836 KB Output is correct
16 Correct 23 ms 21040 KB Output is correct
17 Correct 26 ms 21072 KB Output is correct
18 Correct 25 ms 21136 KB Output is correct
19 Correct 27 ms 21404 KB Output is correct
20 Correct 26 ms 22536 KB Output is correct
21 Correct 23 ms 22808 KB Output is correct
22 Correct 29 ms 22988 KB Output is correct
23 Correct 27 ms 23072 KB Output is correct
24 Correct 26 ms 23072 KB Output is correct
25 Correct 26 ms 23176 KB Output is correct
26 Correct 27 ms 23336 KB Output is correct
27 Correct 27 ms 23872 KB Output is correct
28 Correct 27 ms 24304 KB Output is correct
29 Correct 26 ms 24408 KB Output is correct
30 Correct 37 ms 24412 KB Output is correct
31 Correct 5 ms 24416 KB Output is correct
32 Correct 6 ms 24416 KB Output is correct
33 Correct 6 ms 24416 KB Output is correct
34 Correct 6 ms 24416 KB Output is correct
35 Correct 7 ms 24416 KB Output is correct
36 Correct 4 ms 24416 KB Output is correct
37 Correct 5 ms 24416 KB Output is correct
38 Correct 5 ms 24416 KB Output is correct
39 Correct 5 ms 24416 KB Output is correct
40 Correct 5 ms 24416 KB Output is correct
41 Correct 7 ms 24416 KB Output is correct
42 Correct 6 ms 24416 KB Output is correct