답안 #59209 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59209	2018-07-21T06:36:13 Z	Mikaeel	Amusement Park (JOI17_amusement_park)	C++14	80 / 100	46 ms	11648 KB

#include "Joi.h"
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define pb push_back
#define bit(x,i) ((x>>i)&1ll)
using namespace std;
typedef long long num;
typedef pair<int,int> point;
const int maxn=1e4+10,lg=60;
vector<int> G[maxn];
int te=0;
num x;
bool mark[maxn];
void dfs(int a){
    mark[a]=1;
    MessageBoard(a,bit(x,te));
    te=(te+1)%lg;
    for(int b:G[a]){
	if(!mark[b]){
	    dfs(b);
	}
    }
}

void Joi(int N, int M, int A[], int B[], num X, int T) {
    x=X;
    for(int i = 0; i < M; i++){
	G[A[i]].pb(B[i]);
	G[B[i]].pb(A[i]);
    }
    dfs(0);
}

#include "Ioi.h"
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define pb push_back
#define bit(x,i) ((x>>i)&1ll)
using namespace std;
typedef long long num;
typedef pair<int,int> point;
const int maxn=1e4+10,lg=60;
vector<int> G0[maxn];
int te0=0;
num x0;
bool mark0[maxn];
int v,t[maxn],size0[maxn],par[maxn];
int root;

void dfs0(int a){
    mark0[a]=1;
    t[a]=te0;
    te0=(te0+1)%lg;
    size0[a]=1;
    for(int b:G0[a]){
	if(!mark0[b]){
	    par[b]=a;
	    dfs0(b);
	    size0[a]+=size0[b];
	}
    }
}
bool vis=0;
void dfs2(int a){
    if(a==root){
	vis=1;
	return;
    }
    mark0[a]=1;
    for(int b:G0[a]){
	if(!mark0[b]){
	    dfs2(b);
	    if(vis) return;
	}
    }
}

int ss=0;
void dfs1(int a){
    if(ss==lg) return;
    mark0[a]=1;
    if(v){
	x0|=1ll<<t[a];
    }
    ss++;
    for(int b:G0[a]){
	if(!mark0[b] && par[a]!=b){
	    v=Move(b);
	    dfs1(b);
	    if(ss==lg) return;
	    v=Move(a);
	}
    }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    v=V;
    for(int i = 0; i < M; i++){
	G0[A[i]].pb(B[i]);
	G0[B[i]].pb(A[i]);
    }
    dfs0(0);
    fill(mark0,mark0+N,0);
    root=P;
    while(size0[root]<lg){
	root=par[root];
	v=Move(root);
    }
    dfs2(0);
    dfs1(root);
    return x0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1264 KB	Output is correct
2	Correct	7 ms	1424 KB	Output is correct
3	Correct	7 ms	1608 KB	Output is correct
4	Correct	6 ms	1836 KB	Output is correct
5	Correct	4 ms	1952 KB	Output is correct
6	Correct	6 ms	1952 KB	Output is correct
7	Correct	6 ms	1952 KB	Output is correct
8	Correct	7 ms	2060 KB	Output is correct
9	Correct	6 ms	2080 KB	Output is correct
10	Correct	6 ms	2080 KB	Output is correct
11	Correct	10 ms	2136 KB	Output is correct
12	Correct	5 ms	2152 KB	Output is correct
13	Correct	6 ms	2152 KB	Output is correct
14	Correct	6 ms	2152 KB	Output is correct
15	Correct	6 ms	2152 KB	Output is correct
16	Correct	6 ms	2152 KB	Output is correct
17	Correct	6 ms	2152 KB	Output is correct
18	Correct	5 ms	2152 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	4528 KB	Output is correct
2	Correct	38 ms	4636 KB	Output is correct
3	Correct	40 ms	4764 KB	Output is correct
4	Correct	25 ms	4872 KB	Output is correct
5	Correct	23 ms	4872 KB	Output is correct
6	Correct	32 ms	4872 KB	Output is correct
7	Correct	28 ms	4872 KB	Output is correct
8	Correct	25 ms	4872 KB	Output is correct
9	Correct	27 ms	4872 KB	Output is correct
10	Correct	24 ms	4872 KB	Output is correct
11	Correct	22 ms	4872 KB	Output is correct
12	Correct	23 ms	4872 KB	Output is correct
13	Correct	23 ms	4872 KB	Output is correct
14	Correct	25 ms	4872 KB	Output is correct
15	Correct	26 ms	4872 KB	Output is correct
16	Correct	24 ms	4872 KB	Output is correct
17	Correct	20 ms	4872 KB	Output is correct
18	Correct	28 ms	4872 KB	Output is correct
19	Correct	27 ms	4872 KB	Output is correct
20	Correct	20 ms	4872 KB	Output is correct
21	Correct	19 ms	4872 KB	Output is correct
22	Correct	26 ms	4872 KB	Output is correct
23	Correct	24 ms	4872 KB	Output is correct
24	Correct	24 ms	4872 KB	Output is correct
25	Correct	27 ms	4872 KB	Output is correct
26	Correct	24 ms	4872 KB	Output is correct
27	Correct	23 ms	4872 KB	Output is correct
28	Correct	28 ms	4872 KB	Output is correct
29	Correct	28 ms	4872 KB	Output is correct
30	Correct	24 ms	4872 KB	Output is correct
31	Correct	6 ms	4872 KB	Output is correct
32	Correct	5 ms	4872 KB	Output is correct
33	Correct	7 ms	4872 KB	Output is correct
34	Correct	5 ms	4872 KB	Output is correct
35	Correct	5 ms	4872 KB	Output is correct
36	Correct	5 ms	4872 KB	Output is correct
37	Correct	6 ms	4872 KB	Output is correct
38	Correct	5 ms	4872 KB	Output is correct
39	Correct	6 ms	4872 KB	Output is correct
40	Correct	5 ms	4872 KB	Output is correct
41	Correct	4 ms	4872 KB	Output is correct
42	Correct	5 ms	4872 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
52.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	4872 KB	Output is correct
2	Correct	37 ms	5152 KB	Output is correct
3	Correct	46 ms	5512 KB	Output is correct
4	Correct	27 ms	5704 KB	Output is correct
5	Partially correct	22 ms	5704 KB	Partially correct
6	Correct	22 ms	5704 KB	Output is correct
7	Correct	27 ms	5704 KB	Output is correct
8	Correct	34 ms	5704 KB	Output is correct
9	Correct	27 ms	5704 KB	Output is correct
10	Correct	19 ms	5736 KB	Output is correct
11	Correct	23 ms	6016 KB	Output is correct
12	Correct	24 ms	6136 KB	Output is correct
13	Correct	23 ms	6172 KB	Output is correct
14	Correct	19 ms	6292 KB	Output is correct
15	Correct	28 ms	6536 KB	Output is correct
16	Correct	23 ms	6720 KB	Output is correct
17	Correct	25 ms	6928 KB	Output is correct
18	Partially correct	20 ms	7120 KB	Partially correct
19	Correct	23 ms	7404 KB	Output is correct
20	Correct	20 ms	7840 KB	Output is correct
21	Correct	20 ms	8096 KB	Output is correct
22	Correct	26 ms	8336 KB	Output is correct
23	Correct	28 ms	8528 KB	Output is correct
24	Correct	26 ms	8624 KB	Output is correct
25	Correct	24 ms	8964 KB	Output is correct
26	Correct	28 ms	9240 KB	Output is correct
27	Correct	26 ms	9280 KB	Output is correct
28	Correct	26 ms	9324 KB	Output is correct
29	Correct	23 ms	9472 KB	Output is correct
30	Correct	24 ms	9644 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	10652 KB	Output is correct
2	Correct	40 ms	11168 KB	Output is correct
3	Correct	41 ms	11504 KB	Output is correct
4	Correct	25 ms	11648 KB	Output is correct
5	Incorrect	26 ms	11648 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

답안 #59209

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