oj.uz

Submission #533741

# Submission time Handle Problem Language Result Execution time Memory
533741 2022-03-07T05:18:32 Z 79brue None (JOI16_dungeon2) C++14
44 / 100
 12 ms 6852 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];
bool isOriginal[40002];
int num[40002];

void dfs(int x, int parNum = -1){
    prvNum[x] = LastRoad();
    deg[x] = NumberOfRoads();

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

    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);
            continue;
        }
        Move(i, 2);
        link[x].push_back(++n);
        dfs(n, x);
    }
    if(prvNum[x] > 0) Move(prvNum[x], 2);
}

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){
    if(isOriginal[x]){ /// 고유한 정점
        num[x] = x;
        for(int i=1; i<=deg[x]; i++){
            if(i==prvNum[x]) continue;
            Move(i, getBit(idx[x], bit));
            dfs2(link[x][i], bit);
        }
        if(prvNum[x] > 0) Move(prvNum[x], 2);
    }
    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);
    dfs(++n);
    for(int i=0; i<5; i++){
        dfs2(1, i);
    }
    assert(origCnt <= 200);

    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]]){
            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 6 ms 6476 KB Output is correct
2 Correct 6 ms 6476 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 6 ms 6476 KB Output is correct
7 Correct 5 ms 6476 KB Output is correct
8 Correct 5 ms 6476 KB Output is correct
9 Correct 5 ms 6476 KB Output is correct
10 Correct 5 ms 6476 KB Output is correct
11 Correct 5 ms 6476 KB Output is correct
12 Correct 8 ms 6476 KB Output is correct
13 Correct 5 ms 6476 KB Output is correct
14 Correct 5 ms 6476 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6852 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -