| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 134663 |
2019-07-23T06:50:33 Z |
임유진(#3241) |
None (JOI16_dungeon2) |
C++14 |
|
35 ms |
1528 KB |
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 205;
static int par[MAXN], dep[MAXN], parroad[MAXN];
static vector<int> ed[MAXN];
static int N;
static int dis[MAXN][MAXN];
static int cnt[MAXN];
int anc(int x, int d) {
while(dep[x] > d) x = par[x];
return x;
}
void dfs(int x) {
int k = NumberOfRoads();
parroad[x] = LastRoad();
//printf("x = %d, k = %d, parroad = %d, par = %d, dep = %d\n", x, k, parroad[x], par[x], dep[x]);
for(int i = 1; i <= k; i++) if(i != parroad[x]) {
Move(i, 2);
int c = Color();
//printf("c = %d\n", c);
if(c == 1) {
N++;
ed[x].push_back(N);
ed[N].push_back(x);
par[N] = x;
dep[N] = dep[x] + 1;
dfs(N);
}
else if(c == 2) {
int toend = LastRoad();
Move(toend, 1);
int y = x;
while(Color() != 1) {
Move(parroad[y], 2);
y = par[y];
}
ed[x].push_back(y);
ed[y].push_back(x);
Move(toend, 2);
}
else Move(LastRoad(), 3);
}
if(parroad[x] != -1) Move(parroad[x], 3);
}
void Inspect(int R) {
dep[1] = 2;
N = 1;
dfs(1);
/*
for(int i = 1; i <= N; i++) {
printf("ed[%d] = [", i);
for(auto a : ed[i]) printf("%d ", a);
printf("]\n");
}
*/
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(auto a : ed[i]) dis[i][a] = 1;
for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
if(dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];
//for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) printf("dis[%d][%d] = %d\n", i, j, dis[i][j]);
for(int i = 1; i <= N; i++) for(int j = i + 1; j <= N; 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 |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 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 |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
532 KB |
Output is correct |
| 14 |
Correct |
2 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 |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 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 |
3 ms |
632 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
3 ms |
548 KB |
Output is correct |
| 15 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
976 KB |
Output is correct |
| 2 |
Partially correct |
16 ms |
888 KB |
Partially correct |
| 3 |
Partially correct |
13 ms |
888 KB |
Partially correct |
| 4 |
Incorrect |
35 ms |
1528 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
