| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 501952 | ETK | Dungeon 2 (JOI16_dungeon2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeon2.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
using namespace std;
int d[205],T[205][205],cnt = 1,dis[205][205],ans[205];
//1: Edges on tree, 3: Reverse of 1, 2: nontree edges
int type[205][205];
void dfs(int x){
d[x] = NumberofRoads();
rep(i,1,d[x]){
Move(i,2);
int col = Color(),lst = LastRoad();
type[x][i] = col;
if(col == 1){//not visited yet
T[x][i] = ++cnt;
dfs(cnt);
type[T[x][i]][lst] = 3;
T[T[x][i]][lst] = -1;
}else if(col == 2){
T[x][i] = 0;
}
//Going back
if(col == 1)Move(lst,3);
else Move(lst,col);
}
}
//用三进制分解找到非树边的编号
void work(int x,int pow3){
rep(i,1,d[x]){
if(type[x][i] != 3){
Move(i,x/pow3%3+1);
int lst = LastRoad();
if(type[x][i] == 1)work(T[x][i],pow3);
else T[x][i] += pow3 * (Color() - 1);
Move(lst,color());
}
}
}
void Inspect(int R){
memset(T,-1,sizeof(T));
dfs(1);
int now = 1;
rep(i,0,4){
work(1,now);
now *= 3;
}
memset(dis,0x3f,sizeof(dis));
rep(i,1,cnt)rep(j,1,d[i])
dis[i][T[i][j]] = 1;
rep(i,1,cnt)rep(j,1,cnt)rep(k,1,cnt){
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
rep(i,1,cnt)rep(j,i+1,cnt)
ans[dis[i][j]]++;
rep(i,1,R) Answer(i,ans[i]);
}