oj.uz

답안 #590673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590673 2022-07-06T08:34:39 Z 반딧불(#8412) Amusement Park (JOI17_amusement_park) C++14
10 / 100
 32 ms 5764 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 in[10002], inCnt;

    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;
        in[x] = inCnt++;
        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>>(in[i])%60)&1);
        }
    }
}

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

using namespace std;

typedef long long ll;

namespace{
    const ll INF = (1LL<<60)-1;
    int n, m;
    vector<int> link[10002];

    int depth[10002], par[10002], maxDepth[10002];
    int LCADB[10002][16];
    bool visited[10002];
    bool existPath;
    int in[10002], inCnt, idx[10002];
    int minDist = 10000;
    vector<int> runway;

    int DP[10002];
    int L, R;

    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;
        idx[inCnt] = x;
        in[x] = inCnt++;
        for(auto y: link[x]){
            if(visited[y]) continue;
            dfs2(y);
        }
    }

    int getLCA(int x, int y){
        if(depth[x] > depth[y]) swap(x, y);
        for(int d=0; d<16; d++) if((depth[y]-depth[x]) & (1<<d)) y = LCADB[y][d];
        if(x==y) return x;
        for(int d=15; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
        return par[x];
    }

    int dist(int x, int y){
        return depth[x] + depth[y] - 2*depth[getLCA(x, y)];
    }

    void dfs3(int x){
        DP[x] = (L <= x && x <= R) ? 1 : 0;
        for(auto y: link[x]){
            dfs3(y);
            DP[x] += DP[y];
        }
    }

    bool dfs4(int x, int avoid, int p=-1){ /// üũ�� ������ ��� �湮�ϵ�, avoid�� ���� �������� �湮�Ѵ�.
        runway.push_back(x);
        if(x == avoid) return true;

        vector<int> linked;
        int dir = -1;
        for(auto y: link[x]) if(y!=p && DP[y]){
            if(dist(x, avoid) == dist(y, avoid)+1) dir = y;
            else linked.push_back(y);
        }
        if(x && par[x]!=p && DP[x]!=60){
            if(dist(x, avoid) == dist(par[x], avoid)+1) dir = par[x];
            else linked.push_back(par[x]);
        }
        if(dir!=-1) linked.push_back(dir);

        bool ret = 0;
        for(auto y: linked){
            if(dfs4(y, avoid, x)) ret = true;
            else runway.push_back(x);
        }
        return ret;
    }

    void trySolution(int l, int r, int x){ /// ���� in, �� in, ������ ��ȣ
        L = l, R = r;
        dfs3(0);
        int validPoints = 1;
        for(int i=0; i<n; i++) if(DP[i] && DP[i] < 60) validPoints++;
        int Farthest = 0, FarDist = -1;
        for(int i=l; i<=r; i++){
            int y = idx[i];
            if(dist(x, y) > FarDist) Farthest = y, FarDist = dist(x, y);
        }
        int len = 2*(validPoints-1) - FarDist;
        if(minDist <= len) return;

        minDist = len;
        runway.clear();
        bool tmp = dfs4(x, Farthest);
//        assert(tmp);
    }
}

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;
    memset(visited, 0, sizeof(visited));
    dfs2(0);
    for(int i=0; i<n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<16; d++) for(int i=0; i<n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    for(int a=max(0, in[x]-59); a<=in[x] && a+59<n; a++){
        int b = a+59;
        trySolution(a, b, x);
    }

    ll ans = 0;
    runway.erase(runway.begin());
    assert((int)runway.size() == minDist);
    for(auto nxt: runway){
        if(V) ans |= (1LL << (in[x]%60));
        V = Move(x = nxt);
    }
    if(V) ans |= (1LL << in[x]%60);
    return ans;
}

Compilation message

Ioi.cpp: In function 'void {anonymous}::trySolution(int, int, int)':
Ioi.cpp:107:14: warning: unused variable 'tmp' [-Wunused-variable]
  107 |         bool tmp = dfs4(x, Farthest);
      |              ^~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1160 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5144 KB Output is correct
2 Correct 22 ms 5208 KB Output is correct
3 Correct 28 ms 5176 KB Output is correct
4 Runtime error 30 ms 5316 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 2 ms 1824 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 3 ms 1828 KB Output is correct
7 Correct 2 ms 1816 KB Output is correct
8 Correct 2 ms 1828 KB Output is correct
9 Correct 11 ms 5708 KB Output is correct
10 Correct 12 ms 5732 KB Output is correct
11 Correct 12 ms 5764 KB Output is correct
12 Correct 1 ms 1032 KB Output is correct
13 Correct 1 ms 1024 KB Output is correct
14 Correct 1 ms 1036 KB Output is correct
15 Correct 1 ms 1028 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5168 KB Output is correct
2 Correct 27 ms 5164 KB Output is correct
3 Correct 22 ms 5156 KB Output is correct
4 Runtime error 27 ms 5324 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5196 KB Output is correct
2 Correct 20 ms 5200 KB Output is correct
3 Correct 23 ms 5196 KB Output is correct
4 Runtime error 32 ms 5344 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -