| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26200 |
2017-06-28T10:28:14 Z |
tlwpdus |
None (JOI16_dungeon2) |
C++ |
|
23 ms |
3048 KB |
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
/*
void Answer(int D, int A)
void Move(int I, int C)
int NumberOfRoads()
int LastRoad()
int Color()
*/
int lis[210][210];
int tis[210][210];
int n;
void dfs(int here) {
int sz = NumberOfRoads(), q, i;
for (i=1;i<=sz;i++) {
bool flag = false;
Move(i,2); q = LastRoad();
if (Color()==1) {
tis[here][i-1] = lis[here][i-1] = n;
dfs(n++);
flag = true;
}
else if (Color()==2) {
tis[here][i-1] = 0;
lis[here][i-1] = -1;
}
else lis[here][i-1] = -2;
Move(q,(flag)?3:Color());
}
}
int getd(int num, int loc) {
int i;
for (i=0;i<loc;i++,num/=3);
return num%3+1;
}
int bit(int dig, int loc) {
int i;
for (i=0;i<loc;i++,dig*=3);
return dig;
}
void adfs(int here, int loc) {
int sz = NumberOfRoads(), q, i;
for (i=1;i<=sz;i++) {
bool flag = false;
if (lis[here][i-1]==-2) {
tis[here][i-1]=lis[here][i-1];
continue;
}
Move(i,getd(here,loc)); q = LastRoad();
if (lis[here][i-1]<0) {
tis[here][i-1] += bit(Color()-1,loc);
}
else {
adfs(lis[here][i-1],loc);
flag = true;
}
Move(q,(flag)?getd(lis[here][i-1],loc):Color());
}
}
void init() {
dfs(n++);
}
const int INF = 987654321;
int mat[220][220];
int res[220];
void floyd() {
int i, j, k;
for (k=0;k<n;k++) {
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
if (mat[i][j]>mat[i][k]+mat[k][j]) {
mat[i][j]=mat[i][k]+mat[k][j];
}
}
}
}
for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (mat[i][j]<=n) res[mat[i][j]]++;
}
void Inspect(int R) {
int i, j;
for (i=0;i<200;i++) for (j=0;j<200;j++) tis[i][j] = -2;
init();
for (i=0;i<n;i++) for (j=0;j<n;j++) if (i!=j) mat[i][j] = INF;
for (i=0;i<5;i++) adfs(0,i);
for (i=0;i<n;i++) for (j=0;j<n;j++) if (tis[i][j]>=0) mat[i][tis[i][j]] = mat[tis[i][j]][i] = 1;
floyd();
for (i=1;i<=R;i++) Answer(i,res[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 11 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 12 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 13 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 14 |
Correct |
0 ms |
3048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 11 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 12 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 13 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 14 |
Correct |
0 ms |
3048 KB |
Output is correct |
| 15 |
Correct |
0 ms |
3048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 2 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 3 |
Partially correct |
9 ms |
3048 KB |
Partially correct |
| 4 |
Partially correct |
16 ms |
3048 KB |
Partially correct |
| 5 |
Partially correct |
0 ms |
3048 KB |
Partially correct |
| 6 |
Partially correct |
3 ms |
3048 KB |
Partially correct |
| 7 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 8 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 9 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 10 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 11 |
Partially correct |
9 ms |
3048 KB |
Partially correct |
| 12 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 13 |
Partially correct |
9 ms |
3048 KB |
Partially correct |
| 14 |
Partially correct |
6 ms |
3048 KB |
Partially correct |
| 15 |
Partially correct |
9 ms |
3048 KB |
Partially correct |
| 16 |
Partially correct |
3 ms |
3048 KB |
Partially correct |
| 17 |
Partially correct |
19 ms |
3048 KB |
Partially correct |
| 18 |
Partially correct |
19 ms |
3048 KB |
Partially correct |
| 19 |
Partially correct |
23 ms |
3048 KB |
Partially correct |
