oj.uz

Submission #533780

# Submission time Handle Problem Language Result Execution time Memory
533780 2022-03-07T08:18:29 Z 79brue None (JOI16_dungeon2) C++14
100 / 100
 26 ms 9972 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

int n;
int deg[40002];
int par[40002], prvNum[40002];
int idx[40002], origCnt;
int origLst[40002];
vector<int> link[40002];
vector<int> toRoot[40002];
bool isOriginal[40002];
int num[40002];

int dfs(int x, int parNum = -1){
//    printf("dfs %d %d\n", x, parNum);
    prvNum[x] = LastRoad();
    deg[x] = NumberOfRoads();

    if(Color() != 1){ /// 이미 방문한 정점
        int ret = Color();
        Move(LastRoad(), Color());
        return ret;
    }

    isOriginal[x] = 1;
    idx[x] = ++origCnt;
    origLst[origCnt] = x;

    for(int i=1; i<=deg[x]; i++){
        if(i == prvNum[x]){
            par[x] = parNum;
            link[x].push_back(parNum);
            toRoot[x].push_back(1);
            continue;
        }
        Move(i, 2);
        link[x].push_back(++n);
        int tmp = dfs(n, x);
        toRoot[x].push_back(tmp==2);
    }

    if(prvNum[x] > 0) Move(prvNum[x], 3);
    return 3;
}

int getBit(int x, int y){
    while(y--) x/=3;
    return x%3+1;
}

int pow3[] = {1, 3, 9, 27, 81, 243};

void dfs2(int x, int bit){
//    printf("dfs2 %d %d\n", x, bit);
    if(isOriginal[x]){ /// 고유한 정점
        num[x] = x;
        for(int i=1; i<=deg[x]; i++){
            if(i==prvNum[x] || toRoot[x][i]) continue;
            Move(i, getBit(idx[x], bit));
            dfs2(link[x][i], bit);
        }
        if(prvNum[x] > 0) Move(prvNum[x], getBit(idx[x], bit));
    }
    else{
        num[x] += (Color() - 1) * pow3[bit];
        Move(LastRoad(), Color());
    }
}

int dist[1002][1002];
int ans[1002];

void Inspect(int R){
    for(int i=0; i<=40000; i++) link[i].push_back(0), toRoot[i].push_back(0);
    dfs(++n);
    for(int i=0; i<5; i++){
        dfs2(1, i);
    }

    for(int i=0; i<=1000; i++) for(int j=0; j<=1000; j++) if(i!=j) dist[i][j] = 1e9;

    for(int i=1; i<=origCnt; i++){
        for(auto y: link[origLst[i]]){
            if(y==0) continue;
//            printf("%d %d\n", i, isOriginal[y] ? idx[y] : num[y]);
            dist[i][isOriginal[y] ? idx[y] : num[y]] = 1;
            dist[isOriginal[y] ? idx[y] : num[y]][i] = 1;
        }
    }

    for(int k=1; k<=origCnt; k++){
        for(int i=1; i<=origCnt; i++){
            for(int j=1; j<=origCnt; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for(int i=1; i<=origCnt; i++) for(int j=i+1; j<=origCnt; j++) ans[dist[i][j]]++;
    for(int i=1; i<=R; i++) Answer(i, ans[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8652 KB Output is correct
2 Correct 11 ms 8652 KB Output is correct
3 Correct 7 ms 8652 KB Output is correct
4 Correct 8 ms 8652 KB Output is correct
5 Correct 7 ms 8652 KB Output is correct
6 Correct 9 ms 8724 KB Output is correct
7 Correct 7 ms 8740 KB Output is correct
8 Correct 8 ms 8652 KB Output is correct
9 Correct 7 ms 8652 KB Output is correct
10 Correct 7 ms 8652 KB Output is correct
11 Correct 7 ms 8652 KB Output is correct
12 Correct 7 ms 8652 KB Output is correct
13 Correct 7 ms 8652 KB Output is correct
14 Correct 7 ms 8740 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8652 KB Output is correct
2 Correct 7 ms 8716 KB Output is correct
3 Correct 7 ms 8652 KB Output is correct
4 Correct 7 ms 8652 KB Output is correct
5 Correct 7 ms 8652 KB Output is correct
6 Correct 9 ms 8760 KB Output is correct
7 Correct 8 ms 8680 KB Output is correct
8 Correct 7 ms 8652 KB Output is correct
9 Correct 7 ms 8652 KB Output is correct
10 Correct 7 ms 8652 KB Output is correct
11 Correct 7 ms 8652 KB Output is correct
12 Correct 7 ms 8652 KB Output is correct
13 Correct 7 ms 8652 KB Output is correct
14 Correct 7 ms 8724 KB Output is correct
15 Correct 7 ms 8652 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9056 KB Output is correct
2 Correct 17 ms 9072 KB Output is correct
3 Correct 15 ms 9124 KB Output is correct
4 Correct 26 ms 9888 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 11 ms 8908 KB Output is correct
7 Correct 18 ms 9036 KB Output is correct
8 Correct 17 ms 9092 KB Output is correct
9 Correct 15 ms 9084 KB Output is correct
10 Correct 15 ms 9036 KB Output is correct
11 Correct 16 ms 9036 KB Output is correct
12 Correct 15 ms 9100 KB Output is correct
13 Correct 17 ms 9292 KB Output is correct
14 Correct 15 ms 9052 KB Output is correct
15 Correct 15 ms 9036 KB Output is correct
16 Correct 11 ms 9036 KB Output is correct
17 Correct 24 ms 9932 KB Output is correct
18 Correct 24 ms 9972 KB Output is correct
19 Correct 24 ms 9932 KB Output is correct