oj.uz

Submission #51780

# Submission time Handle Problem Language Result Execution time Memory
51780 2018-06-21T07:10:39 Z ainta Amusement Park (JOI17_amusement_park) C++17
0 / 100
 3000 ms 786432 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_];
	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;
		for (auto &x : E[a]) {
			if (x != pp) {
				Dep[x] = Dep[a] + 1;
				DFS(x, a);
				D[a] = max(D[a], D[x] + 1);
				C[a] += C[x];
			}
		}
		vector<point>V;
		for (auto &x : E[a]) {
			if (x != pp) {
				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_];
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;
	for (auto &x : E[a]) {
		if (x != pp) {
			Dep[x] = Dep[a] + 1;
			DFS(x, a);
			D[a] = max(D[a], D[x] + 1);
			C[a] += C[x];
			par[x] = a;
		}
	}
	vector<point>V;
	for (auto &x : E[a]) {
		if (x != pp) {
			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)ck = 1;
	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;
		}
	}
	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) {
		T = Move(par[a]);
		a = par[a];
	}
	Add(a, T);
	if (D[a] >= 60) {
		for (i = 0; i < 59; i++) {
			T = Move(G[a][0]);
			a = G[a][0];
			Add(a, T);
		}
		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:62:6: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
  int ck = 0;
      ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1896 KB Output is correct
2 Incorrect 6 ms 2028 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3113 ms 393216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 786432 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 393216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3116 ms 393216 KB Time limit exceeded
2 Halted 0 ms 0 KB -