답안 #362811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362811	2021-02-04T12:39:16 Z	denkendoemeer	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	28 ms	6328 KB

#include<bits/stdc++.h>
#include "Joi.h"
#define ll long long
using namespace std;
vector<int>g[20005];
int tin[20005],u=0;
bool viz[200005];
void dfs(int nod,ll x)
{
    viz[nod]=1;
    tin[nod]=u++;
    int num=tin[nod]%60;
    MessageBoard(nod,(x>>num)&1);
    for(auto it:g[nod]){
        if (viz[it]==0)
            dfs(it,x);
    }
}
void Joi(int n,int m,int a[],int b[],ll x,int t)
{
    int i;
    for(i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0,x);
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#include "Ioi.h"
vector<int>g[20005];
int tin[20005],cnt[20005],t[20005],u=0,v[60],ans[20005],h[20005];
bool viz[20005],w[20005];
vector<int>tree[20005];
void dfs(int nod)
{
    viz[nod]=1;
    cnt[nod]=1;
    tin[nod]=u++;
    for(auto it:g[nod]){
        if (viz[it]==0){
            dfs(it);
            t[it]=nod;
            tree[nod].push_back(it);
            cnt[nod]+=cnt[it];
        }
    }
}
int cur;
void dfs2(int nod,int ta)
{
    if (cur==60)
        return ;
    ++cur;
    int num=tin[nod]%60;
    w[nod]=v[num]==-1;
    h[nod]=0;
    for(auto it:tree[nod]){
        dfs2(it,nod);
        w[nod]|=w[it];
        h[nod]=max(h[nod],h[it]+1);
    }
}
void dfs3(int nod,int tat,bool oki)
{
    if (tree[nod].empty())
        return ;
    int maxi=-1;
    for(auto it:tree[nod]){
        if (w[it]){
            if (maxi==-1 || h[maxi]<h[it])
                maxi=it;
        }
    }
    if (oki && maxi!=-1){
        for(auto it:tree[nod]){
            if (w[it] && it!=maxi){
                v[tin[it]%60]=it;
                ans[it]=Move(it);
                dfs3(it,nod,0);
                Move(nod);
            }
        }
        v[tin[maxi]%60]=maxi;
        ans[maxi]=Move(maxi);
        dfs3(maxi,nod,1);
    }
    else{
        for(auto it:tree[nod]){
            if (w[it]){
                v[tin[it]%60]=it;
                ans[it]=Move(it);
                dfs3(it,nod,0);
                Move(nod);
            }
        }
    }
}
ll Ioi(int n,int m,int a[],int b[],int x,int y,int st)
{
    int i;
    for(i=0;i<60;i++)
        v[i]=-1;
    for(i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0);
    ans[x]=y;
    v[tin[x]%60]=x;
    while(cnt[x]<60){
        x=t[x];
        ans[x]=Move(x);
        v[tin[x]%60]=x;
    }
    dfs2(x,t[x]);
    if (w[x])
        dfs3(x,t[x],1);
    ll rez=0;
    for(i=0;i<60;i++)
        rez=rez+(1LL<<i)*ans[v[i]];
    return rez;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	2 ms	2280 KB	Output is correct
3	Correct	2 ms	2416 KB	Output is correct
4	Correct	2 ms	2280 KB	Output is correct
5	Correct	2 ms	2280 KB	Output is correct
6	Correct	2 ms	2408 KB	Output is correct
7	Correct	2 ms	2332 KB	Output is correct
8	Correct	2 ms	2516 KB	Output is correct
9	Correct	2 ms	2288 KB	Output is correct
10	Correct	2 ms	2280 KB	Output is correct
11	Correct	6 ms	2628 KB	Output is correct
12	Correct	2 ms	2656 KB	Output is correct
13	Correct	2 ms	2288 KB	Output is correct
14	Correct	2 ms	2416 KB	Output is correct
15	Correct	2 ms	2512 KB	Output is correct
16	Correct	2 ms	2512 KB	Output is correct
17	Correct	2 ms	2512 KB	Output is correct
18	Correct	3 ms	2288 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	6276 KB	Output is correct
2	Correct	27 ms	6020 KB	Output is correct
3	Correct	28 ms	6180 KB	Output is correct
4	Correct	16 ms	4252 KB	Output is correct
5	Correct	18 ms	5020 KB	Output is correct
6	Correct	20 ms	4636 KB	Output is correct
7	Correct	18 ms	4768 KB	Output is correct
8	Correct	17 ms	4892 KB	Output is correct
9	Correct	17 ms	5116 KB	Output is correct
10	Correct	15 ms	4256 KB	Output is correct
11	Correct	15 ms	4256 KB	Output is correct
12	Correct	16 ms	4272 KB	Output is correct
13	Correct	15 ms	4328 KB	Output is correct
14	Correct	17 ms	4240 KB	Output is correct
15	Correct	18 ms	4380 KB	Output is correct
16	Correct	16 ms	4412 KB	Output is correct
17	Correct	16 ms	4252 KB	Output is correct
18	Correct	16 ms	4380 KB	Output is correct
19	Correct	19 ms	4380 KB	Output is correct
20	Correct	17 ms	4764 KB	Output is correct
21	Correct	14 ms	4904 KB	Output is correct
22	Correct	16 ms	4508 KB	Output is correct
23	Correct	18 ms	5000 KB	Output is correct
24	Correct	17 ms	4508 KB	Output is correct
25	Correct	18 ms	4912 KB	Output is correct
26	Correct	16 ms	4764 KB	Output is correct
27	Correct	17 ms	4992 KB	Output is correct
28	Correct	18 ms	4764 KB	Output is correct
29	Correct	16 ms	4684 KB	Output is correct
30	Correct	16 ms	4496 KB	Output is correct
31	Correct	2 ms	2280 KB	Output is correct
32	Correct	2 ms	2520 KB	Output is correct
33	Correct	2 ms	2288 KB	Output is correct
34	Correct	3 ms	2408 KB	Output is correct
35	Correct	2 ms	2280 KB	Output is correct
36	Correct	2 ms	2404 KB	Output is correct
37	Correct	2 ms	2396 KB	Output is correct
38	Correct	2 ms	2280 KB	Output is correct
39	Correct	2 ms	2280 KB	Output is correct
40	Correct	2 ms	2408 KB	Output is correct
41	Correct	2 ms	2280 KB	Output is correct
42	Correct	2 ms	2280 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2532 KB	Output is correct
2	Correct	2 ms	2408 KB	Output is correct
3	Correct	2 ms	2408 KB	Output is correct
4	Correct	4 ms	2724 KB	Output is correct
5	Correct	4 ms	2724 KB	Output is correct
6	Correct	4 ms	2724 KB	Output is correct
7	Correct	4 ms	2892 KB	Output is correct
8	Correct	4 ms	2852 KB	Output is correct
9	Correct	16 ms	5880 KB	Output is correct
10	Correct	14 ms	5660 KB	Output is correct
11	Correct	15 ms	6008 KB	Output is correct
12	Correct	2 ms	2280 KB	Output is correct
13	Correct	2 ms	2324 KB	Output is correct
14	Correct	2 ms	2324 KB	Output is correct
15	Correct	2 ms	2408 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	6020 KB	Output is correct
2	Correct	28 ms	6184 KB	Output is correct
3	Correct	27 ms	6188 KB	Output is correct
4	Correct	17 ms	4268 KB	Output is correct
5	Correct	19 ms	5496 KB	Output is correct
6	Correct	19 ms	5116 KB	Output is correct
7	Correct	17 ms	4892 KB	Output is correct
8	Correct	17 ms	4696 KB	Output is correct
9	Correct	16 ms	4764 KB	Output is correct
10	Correct	15 ms	4492 KB	Output is correct
11	Correct	16 ms	4256 KB	Output is correct
12	Correct	16 ms	4100 KB	Output is correct
13	Correct	16 ms	4336 KB	Output is correct
14	Correct	16 ms	4112 KB	Output is correct
15	Correct	18 ms	4252 KB	Output is correct
16	Correct	17 ms	4404 KB	Output is correct
17	Correct	16 ms	4252 KB	Output is correct
18	Correct	16 ms	4380 KB	Output is correct
19	Correct	16 ms	4396 KB	Output is correct
20	Correct	16 ms	4948 KB	Output is correct
21	Correct	14 ms	4764 KB	Output is correct
22	Correct	17 ms	5008 KB	Output is correct
23	Correct	17 ms	4764 KB	Output is correct
24	Correct	17 ms	4776 KB	Output is correct
25	Correct	19 ms	4996 KB	Output is correct
26	Correct	18 ms	5004 KB	Output is correct
27	Correct	18 ms	5092 KB	Output is correct
28	Correct	16 ms	4668 KB	Output is correct
29	Correct	16 ms	4612 KB	Output is correct
30	Correct	16 ms	4624 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	6020 KB	Output is correct
2	Correct	28 ms	6328 KB	Output is correct
3	Correct	27 ms	6020 KB	Output is correct
4	Correct	19 ms	4252 KB	Output is correct
5	Correct	19 ms	5532 KB	Output is correct
6	Correct	16 ms	4784 KB	Output is correct
7	Correct	17 ms	4636 KB	Output is correct
8	Correct	18 ms	5020 KB	Output is correct
9	Correct	19 ms	4876 KB	Output is correct
10	Correct	15 ms	4256 KB	Output is correct
11	Correct	15 ms	4500 KB	Output is correct
12	Correct	15 ms	4100 KB	Output is correct
13	Correct	16 ms	4228 KB	Output is correct
14	Correct	16 ms	4112 KB	Output is correct
15	Correct	19 ms	4508 KB	Output is correct
16	Correct	16 ms	4404 KB	Output is correct
17	Correct	17 ms	4396 KB	Output is correct
18	Correct	17 ms	4252 KB	Output is correct
19	Correct	16 ms	4380 KB	Output is correct
20	Correct	14 ms	5052 KB	Output is correct
21	Correct	14 ms	4892 KB	Output is correct
22	Correct	17 ms	4892 KB	Output is correct
23	Correct	22 ms	4636 KB	Output is correct
24	Correct	19 ms	4636 KB	Output is correct
25	Correct	16 ms	4636 KB	Output is correct
26	Correct	16 ms	4636 KB	Output is correct
27	Correct	18 ms	5020 KB	Output is correct
28	Correct	17 ms	5020 KB	Output is correct
29	Correct	16 ms	4772 KB	Output is correct
30	Correct	17 ms	4776 KB	Output is correct
31	Correct	2 ms	2280 KB	Output is correct
32	Correct	2 ms	2520 KB	Output is correct
33	Correct	2 ms	2508 KB	Output is correct
34	Correct	2 ms	2280 KB	Output is correct
35	Correct	3 ms	2280 KB	Output is correct
36	Correct	2 ms	2280 KB	Output is correct
37	Correct	2 ms	2396 KB	Output is correct
38	Correct	2 ms	2280 KB	Output is correct
39	Correct	2 ms	2280 KB	Output is correct
40	Correct	2 ms	2440 KB	Output is correct
41	Correct	2 ms	2280 KB	Output is correct
42	Correct	2 ms	2404 KB	Output is correct

답안 #362811

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