oj.uz

Submission #156500

# Submission time Handle Problem Language Result Execution time Memory
156500 2019-10-06T08:41:29 Z georgerapeanu Amusement Park (JOI17_amusement_park) C++14
100 / 100
 53 ms 6024 KB 
#include "Joi.h"
#pragma once
#include <vector>
#include <functional>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 1e4;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    
    vector<int> graph[NMAX + 5];
    vector<int> children[NMAX + 5];
    int father[NMAX + 5];
    int h[NMAX + 5];

    bool viz[NMAX + 5];
    int lst = 0;

    memset(father,0,sizeof(father));
    memset(h,0,sizeof(h));
    memset(viz,0,sizeof(viz));

    function<void(int,const long long&)> dfs = [&](int nod,const long long &X){
        viz[nod] = true;

        h[nod] = 1;

        for(auto it:graph[nod]){
            if(viz[it] == true){
                continue;
            }
            children[nod].push_back(it);
            father[it] = nod;
            dfs(it,X);
            h[nod] = max(h[nod],1 + h[it]);
        }
    };

    function<void(int,const long long&)> dfs2 = [&](int nod,const long long &X){
        MessageBoard(nod,(X >> lst) & 1);
        lst = (lst + 1) % 60;
    
        for(auto it:children[nod]){
            dfs2(it,X);
        }
    };

    for(int i = 0;i < M;i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    for(int i = 0;i < N;i++){
        sort(graph[i].begin(),graph[i].end());
    }

    dfs(1,X);
    
    for(int i = 0;i < N;i++){
        sort(children[i].begin(),children[i].end(),[&](int a,int b){return h[a] > h[b];});
    }

    dfs2(1,X);
}

#include "Ioi.h"
#pragma once
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e4;

vector<int> graph[NMAX + 5];
vector<int> children[NMAX + 5];
int father[NMAX + 5];
int h[NMAX + 5];
int w[NMAX + 5];

bool viz[NMAX + 5];
int wut[NMAX + 5];
int lst = 0;

void dfs(int nod){
    viz[nod] = true;

    w[nod] = h[nod] = 1;

    for(auto it:graph[nod]){
        if(viz[it] == true){
            continue;
        }
        children[nod].push_back(it);
        father[it] = nod;
        dfs(it);
        w[nod] += w[it];
        h[nod] = max(h[nod],1 + h[it]);
    }
}

void dfs2(int nod){
    wut[nod] = lst;
    lst = (lst + 1) % 60;

    for(auto it:children[nod]){
        dfs2(it);
    }
}

int lim = 60;
bool take[NMAX + 5];

void dfs3(int nod){
    lim--;
    if(lim < 0){
        return;
    }

    take[nod] = true;
    
    for(auto it:children[nod]){
        dfs3(it);
    }
}

long long ans = 0;
long long v,p;

void dfs4(int nod){
    ans |= (v << wut[p]);
    
    for(auto it:children[nod]){
        if(take[it]){
            v = Move(p = it);
            dfs4(it);
            v = Move(p = nod);
        }
    }
}

void dfs5(int nod){
    ans |= (v << wut[p]);

    if(children[nod].empty() || take[children[nod][0]] == false){
        return ;
    }

    for(int i = 1;i < (int)children[nod].size();i++){
        if(take[children[nod][i]]){
            v = Move(p = children[nod][i]);
            dfs4(children[nod][i]);
            v = Move(p = nod);
        }
    }

    v = Move(p = children[nod][0]);
    dfs5(children[nod][0]);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i = 0;i < M;i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    for(int i = 0;i < N;i++){
        sort(graph[i].begin(),graph[i].end());
    }

    dfs(1);
    for(int i = 0;i < N;i++){
        sort(children[i].begin(),children[i].end(),[&](int a,int b){return h[a] > h[b];});
    }

    dfs2(1);

    ans |= (((long long)V) << (wut[P]));

    while(w[P] < 60){
        V = Move(father[P]);
        P = father[P];
        ans |= (((long long)V) << (wut[P]));
    }
    
    v = V;
    p = P;

    dfs3(P);
    dfs5(P);

    return ans;
}

Compilation message

Joi.cpp:2:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Ioi.cpp:2:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1784 KB Output is correct
2 Correct 5 ms 1904 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 5 ms 1840 KB Output is correct
5 Correct 6 ms 1860 KB Output is correct
6 Correct 5 ms 1956 KB Output is correct
7 Correct 5 ms 1924 KB Output is correct
8 Correct 4 ms 1916 KB Output is correct
9 Correct 6 ms 1796 KB Output is correct
10 Correct 5 ms 1908 KB Output is correct
11 Correct 9 ms 2288 KB Output is correct
12 Correct 4 ms 1916 KB Output is correct
13 Correct 5 ms 1916 KB Output is correct
14 Correct 4 ms 1916 KB Output is correct
15 Correct 5 ms 1916 KB Output is correct
16 Correct 6 ms 1952 KB Output is correct
17 Correct 5 ms 1816 KB Output is correct
18 Correct 5 ms 1916 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5696 KB Output is correct
2 Correct 38 ms 5448 KB Output is correct
3 Correct 37 ms 5616 KB Output is correct
4 Correct 23 ms 3888 KB Output is correct
5 Correct 24 ms 5280 KB Output is correct
6 Correct 24 ms 4768 KB Output is correct
7 Correct 24 ms 4504 KB Output is correct
8 Correct 24 ms 4636 KB Output is correct
9 Correct 24 ms 4640 KB Output is correct
10 Correct 20 ms 3740 KB Output is correct
11 Correct 20 ms 3916 KB Output is correct
12 Correct 20 ms 3720 KB Output is correct
13 Correct 20 ms 3868 KB Output is correct
14 Correct 22 ms 3852 KB Output is correct
15 Correct 23 ms 4148 KB Output is correct
16 Correct 24 ms 3992 KB Output is correct
17 Correct 25 ms 3952 KB Output is correct
18 Correct 24 ms 3864 KB Output is correct
19 Correct 24 ms 4096 KB Output is correct
20 Correct 18 ms 4760 KB Output is correct
21 Correct 19 ms 4664 KB Output is correct
22 Correct 24 ms 4220 KB Output is correct
23 Correct 24 ms 4508 KB Output is correct
24 Correct 23 ms 4248 KB Output is correct
25 Correct 24 ms 4632 KB Output is correct
26 Correct 24 ms 4508 KB Output is correct
27 Correct 24 ms 4504 KB Output is correct
28 Correct 24 ms 4664 KB Output is correct
29 Correct 20 ms 4360 KB Output is correct
30 Correct 22 ms 4492 KB Output is correct
31 Correct 4 ms 2012 KB Output is correct
32 Correct 4 ms 1912 KB Output is correct
33 Correct 5 ms 1796 KB Output is correct
34 Correct 4 ms 1912 KB Output is correct
35 Correct 4 ms 1908 KB Output is correct
36 Correct 4 ms 1840 KB Output is correct
37 Correct 4 ms 1864 KB Output is correct
38 Correct 4 ms 1908 KB Output is correct
39 Correct 4 ms 1968 KB Output is correct
40 Correct 5 ms 1908 KB Output is correct
41 Correct 4 ms 1784 KB Output is correct
42 Correct 4 ms 1908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 4 ms 1904 KB Output is correct
3 Correct 4 ms 1904 KB Output is correct
4 Correct 7 ms 2456 KB Output is correct
5 Correct 7 ms 2448 KB Output is correct
6 Correct 7 ms 2448 KB Output is correct
7 Correct 7 ms 2600 KB Output is correct
8 Correct 7 ms 2336 KB Output is correct
9 Correct 19 ms 5972 KB Output is correct
10 Correct 19 ms 5872 KB Output is correct
11 Correct 19 ms 5948 KB Output is correct
12 Correct 4 ms 1916 KB Output is correct
13 Correct 4 ms 1916 KB Output is correct
14 Correct 5 ms 1828 KB Output is correct
15 Correct 4 ms 1868 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5500 KB Output is correct
2 Correct 37 ms 5896 KB Output is correct
3 Correct 37 ms 6016 KB Output is correct
4 Correct 23 ms 3892 KB Output is correct
5 Correct 25 ms 5252 KB Output is correct
6 Correct 24 ms 4504 KB Output is correct
7 Correct 24 ms 4376 KB Output is correct
8 Correct 24 ms 4768 KB Output is correct
9 Correct 25 ms 4644 KB Output is correct
10 Correct 20 ms 3704 KB Output is correct
11 Correct 20 ms 3968 KB Output is correct
12 Correct 20 ms 3804 KB Output is correct
13 Correct 20 ms 3716 KB Output is correct
14 Correct 22 ms 3720 KB Output is correct
15 Correct 25 ms 4120 KB Output is correct
16 Correct 24 ms 4128 KB Output is correct
17 Correct 24 ms 3740 KB Output is correct
18 Correct 25 ms 4000 KB Output is correct
19 Correct 23 ms 4132 KB Output is correct
20 Correct 19 ms 4816 KB Output is correct
21 Correct 19 ms 4768 KB Output is correct
22 Correct 23 ms 4504 KB Output is correct
23 Correct 24 ms 4504 KB Output is correct
24 Correct 24 ms 4640 KB Output is correct
25 Correct 24 ms 4620 KB Output is correct
26 Correct 24 ms 4640 KB Output is correct
27 Correct 24 ms 4376 KB Output is correct
28 Correct 24 ms 4396 KB Output is correct
29 Correct 22 ms 4444 KB Output is correct
30 Correct 24 ms 4472 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5616 KB Output is correct
2 Correct 38 ms 5740 KB Output is correct
3 Correct 37 ms 6024 KB Output is correct
4 Correct 23 ms 3988 KB Output is correct
5 Correct 24 ms 5616 KB Output is correct
6 Correct 24 ms 4504 KB Output is correct
7 Correct 24 ms 4768 KB Output is correct
8 Correct 24 ms 4772 KB Output is correct
9 Correct 27 ms 4768 KB Output is correct
10 Correct 23 ms 3852 KB Output is correct
11 Correct 23 ms 3840 KB Output is correct
12 Correct 22 ms 3840 KB Output is correct
13 Correct 22 ms 3720 KB Output is correct
14 Correct 24 ms 3772 KB Output is correct
15 Correct 24 ms 4000 KB Output is correct
16 Correct 22 ms 4024 KB Output is correct
17 Correct 23 ms 3916 KB Output is correct
18 Correct 23 ms 3992 KB Output is correct
19 Correct 23 ms 3864 KB Output is correct
20 Correct 19 ms 4768 KB Output is correct
21 Correct 19 ms 4764 KB Output is correct
22 Correct 24 ms 4512 KB Output is correct
23 Correct 25 ms 4376 KB Output is correct
24 Correct 24 ms 4300 KB Output is correct
25 Correct 24 ms 4504 KB Output is correct
26 Correct 25 ms 4636 KB Output is correct
27 Correct 24 ms 4504 KB Output is correct
28 Correct 24 ms 4376 KB Output is correct
29 Correct 23 ms 4376 KB Output is correct
30 Correct 22 ms 4628 KB Output is correct
31 Correct 4 ms 1780 KB Output is correct
32 Correct 5 ms 1788 KB Output is correct
33 Correct 4 ms 1792 KB Output is correct
34 Correct 4 ms 1996 KB Output is correct
35 Correct 4 ms 1832 KB Output is correct
36 Correct 4 ms 1840 KB Output is correct
37 Correct 4 ms 2040 KB Output is correct
38 Correct 4 ms 2000 KB Output is correct
39 Correct 4 ms 1780 KB Output is correct
40 Correct 4 ms 1964 KB Output is correct
41 Correct 4 ms 1916 KB Output is correct
42 Correct 4 ms 1916 KB Output is correct