| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 134901 |
2019-07-23T11:54:18 Z |
imyujin |
None (JOI16_dungeon2) |
C++14 |
|
24 ms |
1784 KB |
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
static int N;
static int K[MAXN], par[MAXN], parroad[MAXN];
static vector<int> te[MAXN], ne[MAXN], ed[MAXN]; // te => 1 : par, 2 : chi, 3 : back edge, 4 : ancestor
static int thr[6];
static int dis[MAXN][MAXN], cnt[MAXN];
void dfs(int x) {
K[x] = NumberOfRoads();
parroad[x] = LastRoad();
te[x].resize(K[x] + 1);
ne[x].resize(K[x] + 1, 0);
if(parroad[x] != -1) {
te[x][parroad[x]] = 1;
ne[x][parroad[x]] = par[x];
}
for(int i = 1; i <= K[x]; i++) if(te[x][i] != 1) {
Move(i, 2);
if(Color() == 1) {
te[x][i] = 2;
ne[x][i] = ++N;
par[N] = x;
dfs(N);
}
else if(Color() == 2) {
te[x][i] = 3;
Move(LastRoad(), 2);
}
else {
te[x][i] = 4;
Move(LastRoad(), 3);
}
}
if(parroad[x] != -1) Move(parroad[x], 3);
}
void solve(int x, int k) {
//printf("solve(x = %d, k = %d)\n", x, k);
for(int i = 1; i <= K[x]; i++) {
if(te[x][i] == 2) {
Move(i, x / thr[k] % 3 + 1);
solve(ne[x][i], k);
}
else if(te[x][i] == 3) {
Move(i, 1);
int c = Color();
ne[x][i] = ne[x][i] * 3 + c - 1;
Move(LastRoad(), c);
}
}
if(parroad[x] != -1) Move(parroad[x], x / thr[k] % 3 + 1);
}
void Inspect(int R) {
N = 1;
dfs(1);
thr[0] = 1;
for(int i = 1; i < 6; i++) thr[i] = thr[i - 1] * 3;
for(int i = 4; i >= 0; i--) solve(1, i);
for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dis[i][j] = i == j ? 0 : N;
for(int i = 1; i <= N; i++) for(int j = 1; j <= K[i]; j++) if(te[i][j] % 2) {
ed[i].push_back(ne[i][j]);
ed[ne[i][j]].push_back(i);
dis[i][ne[i][j]] = dis[ne[i][j]][i] = 1;
}
/*
for(int i = 1; i <= N; i++) {
printf("i = %d\n", i);
for(int j = 1; j <= K[i]; j++) printf("te = %d, ne = %d\n", te[i][j], ne[i][j]);
}
*/
for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for(int i = 1; i <= N; i++) for(int j = 1; j < i; j++) cnt[dis[i][j]]++;
for(int i = 1; i <= R; i++) Answer(i, cnt[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
508 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
504 KB |
Output is correct |
| 14 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
508 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
12 ms |
892 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
24 ms |
1784 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
760 KB |
Output is correct |
| 7 |
Correct |
12 ms |
888 KB |
Output is correct |
| 8 |
Correct |
12 ms |
892 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 11 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 12 |
Correct |
12 ms |
936 KB |
Output is correct |
| 13 |
Correct |
14 ms |
1160 KB |
Output is correct |
| 14 |
Correct |
12 ms |
888 KB |
Output is correct |
| 15 |
Correct |
12 ms |
888 KB |
Output is correct |
| 16 |
Correct |
6 ms |
888 KB |
Output is correct |
| 17 |
Correct |
23 ms |
1656 KB |
Output is correct |
| 18 |
Correct |
22 ms |
1660 KB |
Output is correct |
| 19 |
Correct |
22 ms |
1656 KB |
Output is correct |
