| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55117 |
2018-07-06T05:22:50 Z |
ainta |
None (JOI16_dungeon2) |
C++17 |
|
27 ms |
1536 KB |
#include "dungeon2.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define N_ 210
int cnt = 0, par[N_], pE[N_], C[N_], S[N_][N_], E[N_][N_], v[N_][N_];
vector<int>Up[N_], Ch[N_], ChN[N_];
void DFS() {
int a = ++cnt;
C[a] = NumberOfRoads();
pE[a] = LastRoad();
int i;
for (i = 1; i <= C[a]; i++) {
if (pE[a] == i)continue;
Move(i, 2);
int c = Color();
if (c == 1) {
par[cnt + 1] = a;
Ch[a].push_back(i);
ChN[a].push_back(cnt + 1);
DFS();
}
else if (c == 2) {
Up[a].push_back(i);
Move(LastRoad(), 2);
}
else {
Move(LastRoad(), 3);
}
}
if (pE[a] != -1) {
Move(pE[a], 3);
}
}
int po[6], res[N_];
void Go(int a, int K) {
for (auto &x : Up[a]) {
Move(x, 1);
S[a][x] += (Color()-1)*K;
Move(LastRoad(), Color());
}
for (int i = 0; i < Ch[a].size(); i++) {
Move(Ch[a][i], (a / K) % 3 + 1);
Go(ChN[a][i], K);
}
if (pE[a] != -1)Move(pE[a], (a / K) % 3 + 1);
}
void Inspect(int R)
{
DFS();
po[0] = 1;
int i, j, k;
for (i = 0; i < 5; i++)po[i + 1] = po[i] * 3;
for (i = 0; i < 5; i++) {
Go(1, po[i]);
}
for (i = 1; i <= cnt; i++)for (j = 1; j <= cnt; j++) {
if (i != j)E[i][j] = 1e9;
else E[i][j] = 0;
}
for (i = 2; i <= cnt; i++) {
E[i][par[i]] = E[par[i]][i] = 1;
}
for (i = 1; i <= cnt; i++) {
for (auto &x : Up[i]) {
E[i][S[i][x]] = E[S[i][x]][i] = 1;
}
}
for (k = 1; k <= cnt; k++)for (i = 1; i <= cnt; i++)for (j = 1; j <= cnt; j++)E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
for (i = 1; i <= cnt; i++)for (j = i + 1; j <= cnt; j++) {
res[E[i][j]]++;
}
for (i = 1; i <= R; i++) {
Answer(i, res[i]);
}
}
Compilation message
dungeon2.cpp: In function 'void Go(int, int)':
dungeon2.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Ch[a].size(); i++) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
508 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
3 ms |
760 KB |
Output is correct |
| 9 |
Correct |
3 ms |
760 KB |
Output is correct |
| 10 |
Correct |
3 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
760 KB |
Output is correct |
| 12 |
Correct |
3 ms |
760 KB |
Output is correct |
| 13 |
Correct |
3 ms |
760 KB |
Output is correct |
| 14 |
Correct |
3 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
760 KB |
Output is correct |
| 4 |
Correct |
3 ms |
760 KB |
Output is correct |
| 5 |
Correct |
3 ms |
760 KB |
Output is correct |
| 6 |
Correct |
3 ms |
768 KB |
Output is correct |
| 7 |
Correct |
2 ms |
944 KB |
Output is correct |
| 8 |
Correct |
2 ms |
944 KB |
Output is correct |
| 9 |
Correct |
3 ms |
944 KB |
Output is correct |
| 10 |
Correct |
2 ms |
944 KB |
Output is correct |
| 11 |
Correct |
2 ms |
944 KB |
Output is correct |
| 12 |
Correct |
2 ms |
944 KB |
Output is correct |
| 13 |
Correct |
3 ms |
944 KB |
Output is correct |
| 14 |
Correct |
2 ms |
944 KB |
Output is correct |
| 15 |
Correct |
3 ms |
944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1276 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1276 KB |
Output is correct |
| 3 |
Correct |
16 ms |
1404 KB |
Output is correct |
| 4 |
Correct |
23 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
13 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
13 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
13 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
18 ms |
1536 KB |
Output is correct |
| 14 |
Correct |
15 ms |
1536 KB |
Output is correct |
| 15 |
Correct |
14 ms |
1536 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1536 KB |
Output is correct |
| 17 |
Correct |
27 ms |
1536 KB |
Output is correct |
| 18 |
Correct |
27 ms |
1536 KB |
Output is correct |
| 19 |
Correct |
25 ms |
1536 KB |
Output is correct |
