Submission #533780

#	Time	Username	Problem	Language	Result	Execution time	Memory
533780		79brue	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	26 ms	9972 KiB

dungeon2

#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 / 17
• Subtask 2: 27 / 27
• Subtask 3: 56 / 56