oj.uz

Submission #156495

# Submission time Handle Problem Language Result Execution time Memory
156495 2019-10-06T08:26:05 Z georgerapeanu Amusement Park (JOI17_amusement_park) C++14
0 / 100
 39 ms 6096 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){
    if(children[nod].empty() || take[children[nod][0]] == false){
        return ;
    }

    ans |= (v << wut[p]);

    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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2052 KB Output is correct
2 Correct 4 ms 2120 KB Output is correct
3 Correct 5 ms 1788 KB Output is correct
4 Incorrect 4 ms 1956 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6016 KB Output is correct
2 Correct 37 ms 5964 KB Output is correct
3 Incorrect 37 ms 5960 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1784 KB Output is correct
2 Correct 4 ms 1780 KB Output is correct
3 Correct 4 ms 1988 KB Output is correct
4 Correct 7 ms 2604 KB Output is correct
5 Correct 7 ms 2584 KB Output is correct
6 Incorrect 7 ms 2544 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 5976 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6064 KB Output is correct
2 Incorrect 39 ms 6096 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -