답안 #39330 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39330	2018-01-11T16:11:18 Z	UncleGrandpa925	Amusement Park (JOI17_amusement_park)	C++14	80 / 100	34 ms	6864 KB

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define bit(x,y) ((x>>(y))&1LL)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

struct dsu {
	int par[NMAX + 5];
	dsu() {
		for (int i = 0; i < NMAX; i++) par[i] = i;
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void uni(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) par[x] = y;
	}
} d;
int Time = 0; int sta[NMAX + 5], par[NMAX + 5];
vector<vector<int> > a(NMAX + 5);
void dfs(int u, int p) {
	sta[u] = ++Time;
	for (auto v : a[u]) {
		if (v == p) continue;
		par[v] = u;
		dfs(v, u);
	}
}
void makeTree(int N, int M, int A[], int B[]) {
	for (int i = 0; i < M; i++) {
		if (d.find(A[i]) != d.find(B[i])) {
			d.uni(A[i], B[i]);
			a[A[i]].push_back(B[i]);
			a[B[i]].push_back(A[i]);
		}
	}
	dfs(0, 0);
}
// end of the common part
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	makeTree(N, M, A, B);
	for (int i = 0; i < N; i++)
		MessageBoard(i, bit(X, sta[i] % 60));
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define bit(x,y) ((x>>(y))&1LL)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

struct dsu {
	int par[NMAX + 5];
	dsu() {
		for (int i = 0; i < NMAX; i++) par[i] = i;
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void uni(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) par[x] = y;
	}
} d;
int Time = 0; int sta[NMAX + 5], par[NMAX + 5];
vector<vector<int> > a(NMAX + 5); int child[NMAX + 5];
int mark[60]; bool visited[NMAX + 5]; int rem;
void dfs(int u, int p) {
	sta[u] = ++Time;
	child[u] = 1;
	for (auto v : a[u]) {
		if (v == p) continue;
		par[v] = u;
		dfs(v, u);
		child[u] += child[v];
	}
}
void makeTree(int N, int M, int A[], int B[]) {
	for (int i = 0; i < M; i++) {
		if (d.find(A[i]) != d.find(B[i])) {
			d.uni(A[i], B[i]);
			a[A[i]].push_back(B[i]);
			a[B[i]].push_back(A[i]);
		}
	}
	dfs(0, 0);
}
int Lab(int u) {
	return sta[u] % 60;
}
void sfd(int u, const int root, int Z) {
	if (mark[Lab(u)] == -1) {
		mark[Lab(u)] = Z; rem--;
	}
	if (rem == 0) return;
	visited[u] = true;
	for (int i = 0; i < a[u].size(); i++) {
		int v = a[u][i];
		if (v == par[u] || visited[v]) continue;
		sfd(v, root, Move(v));
		if (rem == 0) return;
	}
	if (u != root) {
		Move(par[u]);
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	long long ret = 0;
	makeTree(N, M, A, B);
	memset(mark, -1, sizeof(mark)); rem = 60;
	int last = V;
	mark[Lab(P)] = last; rem--;
	while (child[P] < 60 && rem != 0) {
		P = par[P]; last = Move(P);
		if (mark[Lab(P)] == -1) {
			mark[Lab(P)] = last; rem--;
		}
	}
	sfd(P, P, last);
	for (int i = 0; i < 60; i++) {
		if (mark[i] == 1) ret += (1LL << i);
	}
	return ret;
}

Compilation message

Ioi.cpp: In function 'void sfd(int, int, int)':
Ioi.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a[u].size(); i++) {
                    ^

Subtask #1
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	5500 KB	Output is correct
2	Correct	5500 KB	Output is correct
3	Correct	5500 KB	Output is correct
4	Correct	5500 KB	Output is correct
5	Correct	5500 KB	Output is correct
6	Correct	5500 KB	Output is correct
7	Correct	5500 KB	Output is correct
8	Correct	5500 KB	Output is correct
9	Correct	5500 KB	Output is correct
10	Correct	5500 KB	Output is correct
11	Correct	5500 KB	Output is correct
12	Correct	5500 KB	Output is correct
13	Correct	5500 KB	Output is correct
14	Correct	5500 KB	Output is correct
15	Correct	5500 KB	Output is correct
16	Correct	5500 KB	Output is correct
17	Correct	5500 KB	Output is correct
18	Correct	5500 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	6292 KB	Output is correct
2	Correct	28 ms	6292 KB	Output is correct
3	Correct	28 ms	6292 KB	Output is correct
4	Correct	3 ms	6292 KB	Output is correct
5	Correct	13 ms	6280 KB	Output is correct
6	Correct	15 ms	6376 KB	Output is correct
7	Correct	15 ms	6396 KB	Output is correct
8	Correct	22 ms	6468 KB	Output is correct
9	Correct	26 ms	6480 KB	Output is correct
10	Correct	12 ms	6420 KB	Output is correct
11	Correct	18 ms	6420 KB	Output is correct
12	Correct	15 ms	6028 KB	Output is correct
13	Correct	22 ms	6028 KB	Output is correct
14	Correct	16 ms	6028 KB	Output is correct
15	Correct	15 ms	6292 KB	Output is correct
16	Correct	25 ms	6292 KB	Output is correct
17	Correct	15 ms	6292 KB	Output is correct
18	Correct	26 ms	6292 KB	Output is correct
19	Correct	25 ms	6292 KB	Output is correct
20	Correct	12 ms	6332 KB	Output is correct
21	Correct	22 ms	6316 KB	Output is correct
22	Correct	12 ms	6064 KB	Output is correct
23	Correct	22 ms	6200 KB	Output is correct
24	Correct	22 ms	6096 KB	Output is correct
25	Correct	22 ms	6164 KB	Output is correct
26	Correct	22 ms	6216 KB	Output is correct
27	Correct	19 ms	6216 KB	Output is correct
28	Correct	25 ms	6240 KB	Output is correct
29	Correct	19 ms	6152 KB	Output is correct
30	Correct	22 ms	6148 KB	Output is correct
31	Correct	0 ms	5500 KB	Output is correct
32	Correct	0 ms	5500 KB	Output is correct
33	Correct	0 ms	5500 KB	Output is correct
34	Correct	0 ms	5500 KB	Output is correct
35	Correct	0 ms	5500 KB	Output is correct
36	Correct	0 ms	5500 KB	Output is correct
37	Correct	0 ms	5500 KB	Output is correct
38	Correct	0 ms	5500 KB	Output is correct
39	Correct	0 ms	5500 KB	Output is correct
40	Correct	0 ms	5500 KB	Output is correct
41	Correct	0 ms	5500 KB	Output is correct
42	Correct	0 ms	5500 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5500 KB	Output is correct
2	Correct	0 ms	5500 KB	Output is correct
3	Correct	0 ms	5500 KB	Output is correct
4	Correct	0 ms	5764 KB	Output is correct
5	Correct	0 ms	5764 KB	Output is correct
6	Correct	0 ms	5764 KB	Output is correct
7	Correct	0 ms	5764 KB	Output is correct
8	Correct	0 ms	5764 KB	Output is correct
9	Correct	9 ms	6856 KB	Output is correct
10	Correct	6 ms	6856 KB	Output is correct
11	Correct	12 ms	6864 KB	Output is correct
12	Correct	0 ms	5500 KB	Output is correct
13	Correct	0 ms	5500 KB	Output is correct
14	Correct	0 ms	5500 KB	Output is correct
15	Correct	0 ms	5500 KB	Output is correct

Subtask #4
52.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	6292 KB	Output is correct
2	Correct	22 ms	6292 KB	Output is correct
3	Partially correct	32 ms	6292 KB	Partially correct
4	Correct	16 ms	6292 KB	Output is correct
5	Partially correct	15 ms	6556 KB	Partially correct
6	Correct	15 ms	6484 KB	Output is correct
7	Correct	15 ms	6464 KB	Output is correct
8	Correct	9 ms	6296 KB	Output is correct
9	Correct	25 ms	6352 KB	Output is correct
10	Correct	6 ms	6420 KB	Output is correct
11	Correct	12 ms	6420 KB	Output is correct
12	Correct	16 ms	6028 KB	Output is correct
13	Correct	19 ms	6028 KB	Output is correct
14	Correct	22 ms	6028 KB	Output is correct
15	Correct	22 ms	6292 KB	Output is correct
16	Correct	15 ms	6292 KB	Output is correct
17	Correct	18 ms	6292 KB	Output is correct
18	Partially correct	22 ms	6292 KB	Partially correct
19	Correct	19 ms	6292 KB	Output is correct
20	Correct	12 ms	6328 KB	Output is correct
21	Correct	15 ms	6316 KB	Output is correct
22	Correct	15 ms	6184 KB	Output is correct
23	Correct	12 ms	6132 KB	Output is correct
24	Correct	22 ms	6128 KB	Output is correct
25	Correct	18 ms	6208 KB	Output is correct
26	Correct	12 ms	6192 KB	Output is correct
27	Correct	22 ms	6280 KB	Output is correct
28	Correct	22 ms	6080 KB	Output is correct
29	Correct	15 ms	6128 KB	Output is correct
30	Correct	22 ms	6176 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	6292 KB	Output is correct
2	Correct	27 ms	6292 KB	Output is correct
3	Incorrect	27 ms	6292 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

답안 #39330

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 52.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
52.0 / 55.0

Subtask #5
0 / 17.0