# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
501956 | 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;
const int inf = 0x3f3f3f3f;
int d[205],T[205][205],cnt = 1,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
Move(lst,col == 1 ? 3: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;
}
vector <int> G[205];
rep(i,1,cnt)rep(j,1,d[i]){
int x = T[i][j];
if(x != -1){
G[i].push_back(x);
G[x].push_back(i);
}
}
queue <int> q;
rep(i,1,cnt){
vector <int> dis(n+1,inf);
dis[i] = 0;q.push(i);
while(!q.empty()){
int u = q.front();q.pop();
if(dis[u] == R)continue;
for(auto v:G[u]){
if(dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1;
++ans[dis[v]];
q.push(v);
}
}
}
}
rep(i,1,R) Answer(i,ans[i]/2);
}