oj.uz

Submission #590538

# Submission time Handle Problem Language Result Execution time Memory
590538 2022-07-06T05:55:52 Z 반딧불(#8412) Amusement Park (JOI17_amusement_park) C++14
10 / 100
 27 ms 5940 KB 
#include "Joi.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

namespace{
    int n, m;
    vector<int> link[10002];

    int depth[10002], par[10002], maxDepth[10002];
    bool visited[10002];
    bool existPath;
    int idx[10002], idxCnt;

    void dfs(int x, int dp=0){
        visited[x] = 1;
        depth[x] = dp;
        vector<int> newLink;
        for(auto y: link[x]){
            if(visited[y]) continue;
            newLink.push_back(y);
            par[y] = x;
            dfs(y, dp+1);
            maxDepth[x] = max(maxDepth[x], maxDepth[y]+1);
        }
        link[x].swap(newLink);
    }

    void dfs2(int x){
        visited[x] = 1;
        if(idxCnt < 60) idx[x] = idxCnt++;
        for(auto y: link[x]){
            if(visited[y]) continue;
            dfs2(y);
        }
    }
}

void Joi(int N, int M, int A[], int B[], ll X, int T) {
    n = N, m = M;
    for(int i=0; i<m; i++){
        link[A[i]].push_back(B[i]);
        link[B[i]].push_back(A[i]);
    }
    dfs(0);
    existPath = (maxDepth[0] >= 59);
    if(existPath){
        for(int i=0; i<n; i++){
            MessageBoard(i, (X>>(depth[i]%60))&1);
        }
    }
    else{
        memset(visited, 0, sizeof(visited));
        dfs2(0);
        for(int i=0; i<n; i++){
            MessageBoard(i, (X>>idx[i])&1);
        }
    }
}

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace{
    int n, m;
    vector<int> link[10002];

    int depth[10002], par[10002], maxDepth[10002];
    bool visited[10002];
    bool existPath;
    int idx[10002], idxCnt;

    void dfs(int x, int dp=0){
        visited[x] = 1;
        depth[x] = dp;
        vector<int> newLink;
        for(auto y: link[x]){
            if(visited[y]) continue;
            newLink.push_back(y);
            par[y] = x;
            dfs(y, dp+1);
            maxDepth[x] = max(maxDepth[x], maxDepth[y]+1);
        }
        link[x].swap(newLink);
    }

    void dfs2(int x){
        visited[x] = 1;
        if(idxCnt < 60) idx[x] = idxCnt++;
        for(auto y: link[x]){
            if(visited[y]) continue;
            dfs2(y);
        }
    }
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T){
    n = N, m = M;
    for(int i=0; i<m; i++){
        link[A[i]].push_back(B[i]);
        link[B[i]].push_back(A[i]);
    }
    dfs(0);
    existPath = (maxDepth[0] >= 59);

    if(existPath){ /// �ö󰬴� �������� ��
        int x = P;
        ll ans = 0;

        if(depth[x] >= 59){ /// �ö󰡸� ��
            for(int cnt=0; cnt<59; cnt++){
                if(V) ans += (1LL << (depth[x] % 60));
                V = Move(x = par[x]);
            }
            if(V) ans += (1LL << (depth[x] % 60));
            return ans;
        }

        while(x){
            V = Move(x = par[x]);
        }
        for(int cnt=0; cnt<59; cnt++){
            if(V) ans += (1LL << cnt);
            int nxt = -1;
            for(auto y: link[x]){
                if(cnt + maxDepth[y] >= 58){
                    nxt = y;
                    break;
                }
            }
            assert(nxt != -1);
            V = Move(x = nxt);
        }
        if(V) ans += (1LL << 59);
        return ans;
    }

    /// ���� ��Ʈ���� �ö�
    int x = P;
    ll ans = 0;
    while(x) V = Move(x = par[x]);

}

Compilation message

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:84:8: warning: unused variable 'ans' [-Wunused-variable]
   84 |     ll ans = 0;
      |        ^~~
Ioi.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5484 KB Output is correct
2 Correct 25 ms 5652 KB Output is correct
3 Correct 24 ms 5540 KB Output is correct
4 Incorrect 14 ms 2932 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1120 KB Output is correct
4 Correct 2 ms 1848 KB Output is correct
5 Correct 3 ms 1916 KB Output is correct
6 Correct 2 ms 1836 KB Output is correct
7 Correct 3 ms 1836 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 18 ms 5912 KB Output is correct
10 Correct 11 ms 5928 KB Output is correct
11 Correct 12 ms 5940 KB Output is correct
12 Correct 0 ms 1036 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 0 ms 1032 KB Output is correct
15 Correct 0 ms 1036 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5604 KB Output is correct
2 Correct 22 ms 5624 KB Output is correct
3 Correct 22 ms 5576 KB Output is correct
4 Incorrect 12 ms 2984 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5640 KB Output is correct
2 Correct 20 ms 5556 KB Output is correct
3 Correct 23 ms 5704 KB Output is correct
4 Incorrect 12 ms 2848 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -