답안 #37597 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37597	2017-12-26T09:19:44 Z	grumpy_gordon	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	49 ms	25248 KB

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;

const int maxn = 1e5 + 100;

vector<int> e[maxn];

int n;

int parent[maxn];

int h[maxn];

int get(int x){
  	return x == parent[x] ? x : parent[x] = get(parent[x]);
}

bool uni(int x, int y){
  	x = get(x);
  	y = get(y);
  	if (x == y)
		return 0;
  	parent[x] = y;
  	return 1;
}

int poi[maxn];

void predfs(int v, int par){
  for (auto i : e[v])
	if (i != par)
      	poi[i] = v, h[i] = h[v] + 1, predfs(i, v);
}

pair<int, int> mas[maxn];

vector<int> q[maxn];

int pos[maxn];

bool good[maxn];

void make(int v, int par, int st){
  	q[st].push_back(v);
  	for (auto i : e[v])
		if (i != par && good[i])
			make(i, v, st);
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	n = N;	
	for (int i = 0; i < n; i++)
      parent[i] = i;
  	for (int i = 0; i < M; i++)
	if (uni(A[i], B[i])){
      e[A[i]].push_back(B[i]);
      e[B[i]].push_back(A[i]);
    }
  	predfs(0, -1);
  	for (int i = 0; i < n; i++)
      	mas[i] = make_pair(h[i], i);
  	sort(mas, mas + n);
	for (int i = 0; i < 60; i++)
      	good[mas[i].second] = 1, pos[mas[i].second] = i;
  	for (int i = 0; i < 60; i++)
		make(mas[i].second, -1, mas[i].second);
  	for (int i1 = 60; i1 < n; i1++){
      	int i = mas[i1].second;
      	int v = poi[i];
      	q[i] = q[v];
      	pos[i] = pos[q[i].back()];
      	q[i].pop_back();
      	q[i].insert(q[i].begin(), i);
    }
  	for (int i = 0; i < n; i++)
      MessageBoard(i, ((1ll << pos[i]) & X) > 0);
}

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;

const int maxn = 1e5 + 100;

vector<int> e[maxn];

int n;

int parent[maxn];

int h[maxn];

int get(int x){
  	return x == parent[x] ? x : parent[x] = get(parent[x]);
}

bool uni(int x, int y){
  	x = get(x);
  	y = get(y);
  	if (x == y)
		return 0;
  	parent[x] = y;
  	return 1;
}

int poi[maxn];

void predfs(int v, int par){
  for (auto i : e[v])
	if (i != par)
      	poi[i] = v, h[i] = h[v] + 1, predfs(i, v);
}

pair<int, int> mas[maxn];

vector<int> q[maxn];

int pos[maxn];

bool good[maxn];

void make(int v, int par, int st){
  	q[st].push_back(v);
  	for (auto i : e[v])
		if (i != par && good[i])
			make(i, v, st);
}

long long ans;

int s[60];

void go(int v, int par, vector<int> &g, int &id, int val){
  	s[pos[v]] = val;
  	if (id < 60){
      	for (auto i : e[v])
			if (i == g[id]){
              	id++, go(i, v, g, id, Move(i));
				go(v, par, g, id, val);
              	return;
            }
    }
  	if (par != -1)
		Move(par);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	n = N;	
	for (int i = 0; i < n; i++)
      parent[i] = i;
  	for (int i = 0; i < M; i++)
	if (uni(A[i], B[i])){
      e[A[i]].push_back(B[i]);
      e[B[i]].push_back(A[i]);
    }
  	predfs(0, -1);
  	for (int i = 0; i < n; i++)
      	mas[i] = make_pair(h[i], i);
  	sort(mas, mas + n);
	for (int i = 0; i < 60; i++)
      	good[mas[i].second] = 1, pos[mas[i].second] = i;
  	for (int i = 0; i < 60; i++)
		make(mas[i].second, -1, mas[i].second);
  	for (int i1 = 60; i1 < n; i1++){
      	int i = mas[i1].second;
      	int v = poi[i];
      	q[i] = q[v];
      	pos[i] = pos[q[i].back()];
      	q[i].pop_back();
      	q[i].insert(q[i].begin(), i);
    }
  	int ss = 1;
  	go(P, -1, q[P], ss, V);
  	for (int i = 0; i < 60; i++)
		ans += (1ll << i) * s[i];
  	return ans;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	19024 KB	Output is correct
2	Correct	3 ms	19024 KB	Output is correct
3	Correct	0 ms	19288 KB	Output is correct
4	Correct	3 ms	19024 KB	Output is correct
5	Correct	0 ms	19024 KB	Output is correct
6	Correct	3 ms	19024 KB	Output is correct
7	Correct	3 ms	19288 KB	Output is correct
8	Correct	0 ms	19288 KB	Output is correct
9	Correct	0 ms	19288 KB	Output is correct
10	Correct	3 ms	19024 KB	Output is correct
11	Correct	3 ms	19024 KB	Output is correct
12	Correct	3 ms	19024 KB	Output is correct
13	Correct	0 ms	19288 KB	Output is correct
14	Correct	3 ms	19288 KB	Output is correct
15	Correct	3 ms	19288 KB	Output is correct
16	Correct	3 ms	19288 KB	Output is correct
17	Correct	3 ms	19288 KB	Output is correct
18	Correct	3 ms	19288 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	24568 KB	Output is correct
2	Correct	39 ms	24568 KB	Output is correct
3	Correct	49 ms	24568 KB	Output is correct
4	Correct	15 ms	24832 KB	Output is correct
5	Correct	19 ms	24748 KB	Output is correct
6	Correct	22 ms	24608 KB	Output is correct
7	Correct	28 ms	24628 KB	Output is correct
8	Correct	22 ms	24684 KB	Output is correct
9	Correct	25 ms	24692 KB	Output is correct
10	Correct	6 ms	24696 KB	Output is correct
11	Correct	32 ms	24696 KB	Output is correct
12	Correct	22 ms	24040 KB	Output is correct
13	Correct	27 ms	24040 KB	Output is correct
14	Correct	15 ms	24304 KB	Output is correct
15	Correct	22 ms	24568 KB	Output is correct
16	Correct	25 ms	24568 KB	Output is correct
17	Correct	19 ms	24832 KB	Output is correct
18	Correct	27 ms	24832 KB	Output is correct
19	Correct	32 ms	24832 KB	Output is correct
20	Correct	12 ms	24788 KB	Output is correct
21	Correct	18 ms	24780 KB	Output is correct
22	Correct	18 ms	24568 KB	Output is correct
23	Correct	22 ms	24684 KB	Output is correct
24	Correct	19 ms	24588 KB	Output is correct
25	Correct	25 ms	24648 KB	Output is correct
26	Correct	25 ms	24700 KB	Output is correct
27	Correct	22 ms	24692 KB	Output is correct
28	Correct	19 ms	24712 KB	Output is correct
29	Correct	15 ms	24108 KB	Output is correct
30	Correct	15 ms	24368 KB	Output is correct
31	Correct	3 ms	19024 KB	Output is correct
32	Correct	3 ms	19024 KB	Output is correct
33	Correct	0 ms	19288 KB	Output is correct
34	Correct	0 ms	19024 KB	Output is correct
35	Correct	0 ms	19024 KB	Output is correct
36	Correct	0 ms	19024 KB	Output is correct
37	Correct	0 ms	19024 KB	Output is correct
38	Correct	3 ms	19024 KB	Output is correct
39	Correct	0 ms	19024 KB	Output is correct
40	Correct	0 ms	19024 KB	Output is correct
41	Correct	3 ms	19024 KB	Output is correct
42	Correct	0 ms	19024 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	19024 KB	Output is correct
2	Correct	3 ms	19024 KB	Output is correct
3	Correct	0 ms	19024 KB	Output is correct
4	Correct	0 ms	20080 KB	Output is correct
5	Correct	3 ms	20080 KB	Output is correct
6	Correct	3 ms	20080 KB	Output is correct
7	Correct	3 ms	20080 KB	Output is correct
8	Correct	0 ms	20080 KB	Output is correct
9	Correct	15 ms	25244 KB	Output is correct
10	Correct	18 ms	25248 KB	Output is correct
11	Correct	15 ms	25244 KB	Output is correct
12	Correct	6 ms	19024 KB	Output is correct
13	Correct	3 ms	19024 KB	Output is correct
14	Correct	0 ms	19024 KB	Output is correct
15	Correct	6 ms	19024 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	24568 KB	Output is correct
2	Correct	26 ms	24568 KB	Output is correct
3	Correct	38 ms	24568 KB	Output is correct
4	Correct	22 ms	24832 KB	Output is correct
5	Correct	18 ms	24984 KB	Output is correct
6	Correct	25 ms	24696 KB	Output is correct
7	Correct	26 ms	24680 KB	Output is correct
8	Correct	26 ms	24568 KB	Output is correct
9	Correct	26 ms	24584 KB	Output is correct
10	Correct	25 ms	24696 KB	Output is correct
11	Correct	32 ms	24696 KB	Output is correct
12	Correct	22 ms	24040 KB	Output is correct
13	Correct	22 ms	24040 KB	Output is correct
14	Correct	22 ms	24304 KB	Output is correct
15	Correct	26 ms	24568 KB	Output is correct
16	Correct	32 ms	24568 KB	Output is correct
17	Correct	28 ms	24832 KB	Output is correct
18	Correct	15 ms	24832 KB	Output is correct
19	Correct	39 ms	24832 KB	Output is correct
20	Correct	15 ms	24784 KB	Output is correct
21	Correct	12 ms	24776 KB	Output is correct
22	Correct	27 ms	24672 KB	Output is correct
23	Correct	32 ms	24624 KB	Output is correct
24	Correct	28 ms	24620 KB	Output is correct
25	Correct	32 ms	24692 KB	Output is correct
26	Correct	32 ms	24664 KB	Output is correct
27	Correct	25 ms	24744 KB	Output is correct
28	Correct	25 ms	24584 KB	Output is correct
29	Correct	28 ms	24092 KB	Output is correct
30	Correct	28 ms	24400 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	24568 KB	Output is correct
2	Correct	38 ms	24568 KB	Output is correct
3	Correct	41 ms	24568 KB	Output is correct
4	Correct	22 ms	24832 KB	Output is correct
5	Correct	28 ms	25096 KB	Output is correct
6	Correct	12 ms	24592 KB	Output is correct
7	Correct	28 ms	24568 KB	Output is correct
8	Correct	12 ms	24692 KB	Output is correct
9	Correct	25 ms	24640 KB	Output is correct
10	Correct	22 ms	24696 KB	Output is correct
11	Correct	22 ms	24696 KB	Output is correct
12	Correct	25 ms	24040 KB	Output is correct
13	Correct	12 ms	24040 KB	Output is correct
14	Correct	22 ms	24304 KB	Output is correct
15	Correct	22 ms	24568 KB	Output is correct
16	Correct	28 ms	24568 KB	Output is correct
17	Correct	18 ms	24832 KB	Output is correct
18	Correct	32 ms	24832 KB	Output is correct
19	Correct	32 ms	24832 KB	Output is correct
20	Correct	12 ms	24784 KB	Output is correct
21	Correct	15 ms	24780 KB	Output is correct
22	Correct	36 ms	24648 KB	Output is correct
23	Correct	18 ms	24604 KB	Output is correct
24	Correct	28 ms	24616 KB	Output is correct
25	Correct	27 ms	24624 KB	Output is correct
26	Correct	22 ms	24568 KB	Output is correct
27	Correct	36 ms	24752 KB	Output is correct
28	Correct	41 ms	24772 KB	Output is correct
29	Correct	36 ms	24196 KB	Output is correct
30	Correct	36 ms	24420 KB	Output is correct
31	Correct	0 ms	19024 KB	Output is correct
32	Correct	3 ms	19024 KB	Output is correct
33	Correct	3 ms	19288 KB	Output is correct
34	Correct	3 ms	19024 KB	Output is correct
35	Correct	0 ms	19024 KB	Output is correct
36	Correct	6 ms	19024 KB	Output is correct
37	Correct	0 ms	19024 KB	Output is correct
38	Correct	0 ms	19024 KB	Output is correct
39	Correct	0 ms	19024 KB	Output is correct
40	Correct	0 ms	19024 KB	Output is correct
41	Correct	0 ms	19024 KB	Output is correct
42	Correct	3 ms	19024 KB	Output is correct

답안 #37597

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0