oj.uz

답안 #51782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51782 2018-06-21T07:20:02 Z ainta Amusement Park (JOI17_amusement_park) C++17
8 / 100
 52 ms 8024 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;
		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;
		}
		vector<point>V;
		for (auto &x : E[a]) {
			if (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;
	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;
	}
	vector<point>V;
	for (auto &x : E[a]) {
		if (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)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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1764 KB Output is correct
2 Correct 5 ms 2076 KB Output is correct
3 Correct 5 ms 2232 KB Output is correct
4 Correct 4 ms 2448 KB Output is correct
5 Correct 4 ms 2692 KB Output is correct
6 Correct 4 ms 2728 KB Output is correct
7 Correct 5 ms 2728 KB Output is correct
8 Correct 5 ms 2728 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 5 ms 2904 KB Output is correct
11 Correct 12 ms 2964 KB Output is correct
12 Correct 5 ms 2992 KB Output is correct
13 Correct 7 ms 2992 KB Output is correct
14 Correct 7 ms 2992 KB Output is correct
15 Correct 6 ms 2992 KB Output is correct
16 Correct 6 ms 2992 KB Output is correct
17 Correct 6 ms 2992 KB Output is correct
18 Correct 6 ms 2992 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 7252 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7616 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 7724 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 8024 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -