QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100263 | #408. Dungeon 2 | lmeowdn | 44 | 14ms | 27640kb | C++14 | 1.6kb | 2023-04-25 12:13:02 | 2023-04-25 12:13:03 |
Judging History
answer
#include "dungeon2.h"
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;
const int N=109,inf=0x3f3f3f3f;
int c[N],e[N][N],t[N][N],tot,n=1,fa[N],d[N][N],ans[N],del[N][N];
vi f[N][N],p[1000009];
map<vi,int>mp;
void dfs1(int u) {
c[u]=NumberOfRoads();
fa[u]=LastRoad();
rep(i,1,c[u]) if(i!=fa[u]) {
Move(i,2);
int cc=Color();
if(cc==1) {
++n; e[u][i]=n;
dfs1(n);
} else if(cc==2) {
Move(LastRoad(),cc);
} else {
del[u][i]=1;
Move(LastRoad(),cc);
}
}
if(u!=1) Move(fa[u],3);
}
void dfs2(int u,int x) {
rep(i,1,c[u]) if(i!=fa[u]&&!del[u][i]) {
Move(i,p[u][x]);
if(e[u][i]) dfs2(e[u][i],x);
else {
int cc=Color();
f[u][i].eb(cc);
Move(LastRoad(),cc);
}
} if(u!=1) Move(fa[u],p[u][x]);
}
void Inspect(int R) {
rep(a,1,3) rep(b,1,3) rep(c,1,3)
rep(d,1,3) rep(e,1,3) {
vi tmp={a,b,c,d,e};
mp[tmp]=++tot, p[tot]=tmp;
}
dfs1(1);
rep(i,0,4) dfs2(1,i);
rep(i,1,n) rep(j,1,c[i]) if(!e[i][j]&&!del[i][j]&&j!=fa[i]) e[i][j]=mp[f[i][j]];
rep(i,1,n) rep(j,1,n) d[i][j]=inf;
rep(i,1,n) rep(j,1,c[i]) if(j!=fa[i]&&!del[i][j]) d[i][e[i][j]]=d[e[i][j]][i]=1;
rep(k,1,n) rep(i,1,n) rep(j,1,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
rep(i,1,n) rep(j,i+1,n) ans[d[i][j]]++;
rep(i,1,R) Answer(i,ans[i]);
}
詳細信息
Subtask #1:
score: 17
Accepted
Test #1:
score: 17
Accepted
time: 7ms
memory: 27420kb
input:
10 100 50 7 5 7 10 4 6 2 3 2 1 5 3 1 10 7 2 10 1 3 1 9 2 2 1 7 5 9 6 8 3 1 1 7 2 5 7 3 1 4 3 15 24 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
Accepted: #move = 192
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 27516kb
input:
50 100 50 2 39 10 4 7 43 11 33 2 7 18 1 14 3 46 42 27 2 12 49 4 2 41 3 35 1 37 1 14 4 13 14 19 1 3 22 2 44 1 6 4 49 21 10 36 6 4 9 35 10 37 20 1 49 2 21 29 2 45 25 2 3 28 2 10 38 2 50 14 2 16 13 1 11 1 38 1 41 1 17 2 48 32 3 40 5 48 1 18 1 16 1 49 1 40 1 26 1 2 1 50 2 7 14 1 13 2 8 14 2 23 19 2 45 1...
output:
Accepted: #move = 602
result:
ok
Test #3:
score: 0
Accepted
time: 4ms
memory: 27528kb
input:
50 100 10 2 4 41 1 33 3 25 27 13 2 30 1 4 28 11 8 22 2 36 39 1 10 1 5 2 35 30 2 35 7 2 32 5 1 26 3 49 21 3 4 19 29 20 22 1 23 1 49 2 18 42 2 50 17 1 14 1 14 2 22 13 3 5 14 21 2 28 15 2 29 36 2 3 34 3 12 31 34 1 3 2 5 23 4 24 38 14 40 5 4 45 33 9 39 2 38 26 2 48 11 2 2 30 3 46 25 26 2 9 10 2 6 24 1 5...
output:
Accepted: #move = 616
result:
ok
Test #4:
score: 0
Accepted
time: 14ms
memory: 27624kb
input:
50 100 50 3 5 16 18 1 43 4 46 14 31 38 3 34 22 39 2 1 33 2 12 30 2 41 24 2 29 23 2 45 47 2 15 40 3 50 42 43 2 19 6 2 40 22 3 3 39 22 2 19 10 1 1 1 47 1 1 2 15 12 1 35 2 27 48 3 14 4 13 3 26 39 8 1 7 3 26 29 33 2 23 25 1 21 3 35 40 36 2 25 8 1 6 2 3 42 1 46 3 5 43 25 2 40 4 2 20 28 1 28 1 40 1 3 4 4 ...
output:
Accepted: #move = 644
result:
ok
Test #5:
score: 0
Accepted
time: 8ms
memory: 27580kb
input:
50 100 50 2 11 48 2 25 22 2 7 30 1 40 2 50 37 1 34 3 15 36 3 3 42 21 33 3 10 32 27 2 45 9 3 1 18 32 4 36 13 34 43 4 43 18 21 12 1 45 3 7 31 28 3 50 18 22 2 28 20 4 11 22 13 16 1 50 2 29 17 3 8 13 43 5 2 35 16 18 27 2 36 24 1 23 2 2 26 2 25 41 2 9 22 2 17 15 3 49 20 30 3 3 38 29 2 15 49 3 9 11 39 1 8...
output:
Accepted: #move = 742
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 27508kb
input:
50 100 50 2 31 48 2 22 32 5 11 16 20 40 34 3 13 8 38 2 9 14 4 25 13 9 40 5 50 14 42 49 28 3 4 16 37 5 17 6 26 5 33 5 38 25 45 44 39 7 46 20 48 41 3 16 21 5 47 44 24 18 21 5 24 16 29 6 4 5 50 19 7 36 5 3 26 37 39 6 49 33 11 3 8 13 4 20 9 30 21 5 25 12 32 31 48 5 48 39 28 41 14 6 38 17 27 11 39 3 4 17...
output:
Accepted: #move = 1302
result:
ok
Test #7:
score: 0
Accepted
time: 9ms
memory: 27484kb
input:
32 100 20 5 11 20 30 3 18 5 21 8 22 12 10 5 6 31 16 1 24 5 15 27 29 17 5 5 12 19 26 21 4 5 3 25 14 11 7 5 24 9 28 32 6 5 28 2 24 23 16 5 22 7 21 26 25 5 17 16 31 15 2 5 1 29 27 6 32 5 5 23 13 2 15 5 26 18 12 22 20 5 16 17 6 27 28 5 4 30 20 10 12 5 14 10 3 30 8 5 10 14 25 4 21 5 32 13 23 24 1 5 23 5 ...
output:
Accepted: #move = 1058
result:
ok
Test #8:
score: 0
Accepted
time: 4ms
memory: 27568kb
input:
48 100 50 3 16 39 47 3 3 25 44 3 35 2 44 3 14 31 24 3 29 35 9 3 33 38 29 3 23 16 39 3 11 30 18 3 29 35 5 3 13 26 36 3 28 8 30 3 41 45 22 3 40 20 10 3 27 4 31 3 42 32 17 3 7 1 39 3 15 21 32 3 8 33 38 3 47 34 37 3 22 13 40 3 32 17 46 3 12 40 20 3 43 48 7 3 4 41 45 3 2 44 27 3 10 42 36 3 25 14 31 3 11 ...
output:
Accepted: #move = 914
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 27588kb
input:
44 100 50 3 26 40 32 3 31 14 6 3 18 26 11 3 29 41 16 3 23 7 33 3 31 14 2 3 5 33 18 3 15 43 20 3 17 27 30 3 35 12 23 3 18 26 3 3 20 10 35 3 25 19 36 3 6 2 21 3 24 8 43 3 29 41 4 3 9 30 44 3 7 11 3 3 13 37 36 3 8 35 12 3 14 38 42 3 27 28 39 3 10 5 33 3 41 15 43 3 38 42 13 3 11 3 1 3 9 30 22 3 22 34 39...
output:
Accepted: #move = 838
result:
ok
Test #10:
score: 0
Accepted
time: 10ms
memory: 27512kb
input:
48 100 30 2 6 28 2 28 20 2 35 32 2 26 37 2 22 8 2 33 1 2 27 9 2 5 48 2 7 19 2 24 39 2 48 38 2 21 13 2 12 46 2 16 35 2 31 44 2 29 14 2 23 42 2 44 41 2 9 24 2 2 23 2 30 12 2 34 5 2 20 17 2 19 10 2 42 31 2 39 4 2 40 7 2 1 2 2 47 16 2 37 21 2 25 15 2 3 34 2 36 6 2 32 22 2 3 14 2 46 33 2 4 30 2 11 43 2 1...
output:
Accepted: #move = 578
result:
ok
Test #11:
score: 0
Accepted
time: 6ms
memory: 27576kb
input:
50 100 50 4 42 7 39 27 4 11 9 35 29 4 44 23 8 45 4 23 8 45 48 4 27 37 16 43 4 24 14 21 36 4 40 1 42 39 4 3 4 23 45 4 18 2 11 35 4 34 24 32 38 4 18 2 9 35 4 25 26 28 49 4 48 17 47 19 4 6 44 21 36 4 50 49 20 33 4 27 37 5 43 4 13 47 19 50 4 22 11 9 35 4 48 17 13 47 4 50 49 33 15 4 6 44 14 36 4 25 26 28...
output:
Accepted: #move = 1302
result:
ok
Test #12:
score: 0
Accepted
time: 6ms
memory: 27584kb
input:
50 100 50 4 46 4 5 2 4 5 1 3 4 4 2 5 4 8 4 1 2 5 3 4 4 3 1 2 4 7 8 10 11 4 9 6 11 8 4 7 9 6 3 4 7 10 11 8 4 6 11 13 9 4 9 10 6 7 4 13 14 15 16 4 10 16 15 12 4 16 15 21 12 4 16 14 12 13 4 14 13 15 12 4 19 22 21 18 4 19 20 22 17 4 21 17 20 18 4 18 21 19 22 4 14 17 19 20 4 20 17 24 18 4 27 26 25 24 4 2...
output:
Accepted: #move = 1302
result:
ok
Test #13:
score: 0
Accepted
time: 3ms
memory: 27544kb
input:
50 100 50 4 3 2 6 7 4 47 3 7 1 4 2 1 5 4 4 5 3 9 6 4 7 4 6 3 4 7 1 4 5 4 6 1 5 2 4 10 13 14 9 4 4 8 14 11 4 20 11 12 8 4 12 13 10 9 4 10 14 11 13 4 11 8 14 12 4 13 9 8 12 4 22 17 21 16 4 17 18 22 15 4 19 18 15 16 4 16 17 19 20 4 21 17 18 20 4 18 22 10 19 4 19 22 15 23 4 20 16 21 15 4 21 26 25 27 4 2...
output:
Accepted: #move = 1302
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 27584kb
input:
50 100 50 4 9 10 3 2 4 1 10 4 3 4 1 2 49 4 4 5 6 2 3 4 4 7 13 6 4 4 7 5 8 4 5 8 6 9 4 9 6 10 7 4 7 10 1 8 4 9 2 1 8 4 12 13 15 16 4 11 14 13 16 4 5 12 14 11 4 16 15 12 13 4 14 11 16 23 4 12 11 15 14 4 18 25 19 24 4 19 25 20 17 4 20 18 17 21 4 21 22 18 19 4 20 19 23 22 4 23 20 24 21 4 22 15 21 24 4 2...
output:
Accepted: #move = 1302
result:
ok
Test #15:
score: 0
Accepted
time: 8ms
memory: 27540kb
input:
50 100 50 4 27 2 3 26 4 3 1 27 4 4 4 1 5 2 4 3 5 2 6 4 7 3 6 4 4 5 7 8 4 4 9 8 6 5 4 6 9 10 7 4 8 10 11 7 4 9 11 8 12 4 12 13 9 10 4 11 13 10 14 4 12 14 11 15 4 12 15 13 16 4 17 14 13 16 4 14 44 18 15 4 18 31 15 19 4 20 17 16 19 4 20 18 21 17 4 18 21 22 19 4 20 19 23 22 4 20 23 21 24 4 21 24 22 25 4...
output:
Accepted: #move = 1302
result:
ok
Subtask #2:
score: 27
Accepted
Test #16:
score: 27
Accepted
time: 8ms
memory: 27476kb
input:
10 3 50 4 7 4 10 5 2 8 6 1 10 2 1 9 3 1 7 10 2 7 2 5 6 1 5 8 9 3 7 9 2 4 10 8 7 4 4 1 9 5 3 15 19 9 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
Accepted: #move = 192
result:
ok
Test #17:
score: 0
Accepted
time: 9ms
memory: 27488kb
input:
50 3 50 1 5 1 42 3 48 14 28 1 23 3 36 22 1 2 44 14 3 38 14 26 1 37 2 24 45 2 40 42 1 37 1 33 3 21 23 49 4 3 7 47 6 3 41 39 24 2 40 18 1 38 1 16 1 30 1 22 1 13 3 5 20 28 2 13 4 4 28 37 15 9 1 30 2 7 50 2 30 47 3 24 22 3 3 32 47 40 3 19 27 25 3 35 37 44 3 43 29 33 2 12 32 1 37 1 31 1 5 6 34 46 31 8 24...
output:
Accepted: #move = 602
result:
ok
Test #18:
score: 0
Accepted
time: 7ms
memory: 27572kb
input:
50 3 10 2 28 25 3 23 30 25 3 6 10 46 1 47 1 39 2 3 29 2 28 24 3 41 42 45 1 21 1 3 2 33 38 2 50 38 2 44 17 2 41 31 2 23 20 1 48 4 37 21 50 13 1 49 2 41 31 1 15 2 17 9 1 24 4 48 40 2 15 2 7 22 2 2 1 3 39 30 27 2 36 26 2 7 1 3 6 43 30 5 47 29 26 42 2 2 19 14 1 39 2 41 11 1 39 1 43 1 27 1 17 3 11 49 12 ...
output:
Accepted: #move = 616
result:
ok
Test #19:
score: 0
Accepted
time: 4ms
memory: 27524kb
input:
50 3 50 1 48 2 38 42 2 19 27 1 13 1 46 3 39 34 13 1 50 2 27 22 2 14 39 3 46 40 43 2 12 15 2 11 21 3 44 4 6 2 9 28 1 11 2 27 25 2 42 27 3 24 21 50 3 20 3 32 3 41 19 26 4 43 18 36 12 3 45 44 8 2 42 45 1 18 2 16 35 1 20 5 29 8 3 16 17 3 44 49 14 1 27 1 40 1 50 1 19 1 49 2 6 36 1 25 2 34 21 1 42 1 2 3 6...
output:
Accepted: #move = 644
result:
ok
Test #20:
score: 0
Accepted
time: 8ms
memory: 27504kb
input:
50 3 50 3 18 8 25 3 11 39 45 2 50 36 2 32 23 3 49 42 13 1 40 4 26 17 38 21 1 1 1 20 1 14 1 2 3 22 33 30 2 36 5 2 10 38 3 33 45 43 2 36 38 3 32 46 7 3 1 50 20 2 45 44 2 9 18 1 7 3 39 28 12 2 4 30 2 27 33 2 35 1 2 33 7 4 34 24 31 50 1 22 2 32 43 4 32 23 47 12 3 27 48 32 5 31 4 29 30 17 4 12 15 24 26 1...
output:
Accepted: #move = 742
result:
ok
Test #21:
score: 0
Accepted
time: 14ms
memory: 27600kb
input:
50 3 50 6 37 31 49 13 20 38 1 45 6 15 36 19 11 47 44 3 5 9 26 4 4 33 43 39 1 31 4 18 37 29 35 5 25 49 29 15 47 3 33 43 4 4 35 27 19 21 3 17 13 3 2 31 43 6 1 26 11 35 23 49 5 41 34 30 18 44 3 44 8 3 3 38 48 47 6 45 47 18 29 11 21 5 14 44 7 17 28 5 36 10 3 42 28 2 1 43 3 17 10 28 1 26 4 13 37 35 30 4 ...
output:
Accepted: #move = 1302
result:
ok
Test #22:
score: 0
Accepted
time: 13ms
memory: 27532kb
input:
32 3 20 5 32 18 2 24 20 5 19 14 1 26 5 5 23 25 12 8 22 5 29 9 10 11 27 5 9 29 20 13 2 5 20 10 9 7 32 5 21 22 30 6 25 5 18 32 27 3 10 5 5 4 6 30 19 5 31 6 4 22 8 5 16 30 22 4 12 5 15 17 3 27 11 5 30 16 21 5 26 5 27 2 18 15 29 5 12 26 23 14 16 5 11 13 28 29 15 5 26 12 25 19 30 5 8 1 14 23 31 5 2 27 32...
output:
Accepted: #move = 1058
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 27528kb
input:
48 3 50 3 42 13 38 3 13 6 23 3 46 30 34 3 8 24 47 3 27 19 29 3 2 14 23 3 15 16 41 3 22 12 4 3 45 35 17 3 48 21 27 3 24 47 26 3 37 8 22 3 38 1 2 3 6 23 45 3 39 41 7 3 41 7 36 3 45 35 9 3 25 32 28 3 29 5 40 3 40 25 33 3 36 10 48 3 37 8 12 3 2 14 6 3 4 11 47 3 20 33 18 3 11 46 30 3 10 29 5 3 18 44 32 3...
output:
Accepted: #move = 914
result:
ok
Test #24:
score: 0
Accepted
time: 3ms
memory: 27580kb
input:
44 3 50 3 3 17 40 3 42 15 19 3 13 40 1 3 43 39 9 3 23 18 41 3 22 38 26 3 35 24 8 3 42 15 7 3 43 39 4 3 41 13 32 3 39 20 21 3 17 37 27 3 32 10 3 3 19 25 16 3 8 2 42 3 19 25 14 3 40 1 12 3 30 5 23 3 2 14 16 3 11 22 21 3 11 22 20 3 20 21 6 3 30 5 18 3 29 7 35 3 14 16 33 3 6 34 38 3 12 44 37 3 33 36 31 ...
output:
Accepted: #move = 838
result:
ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 27516kb
input:
48 3 30 2 31 32 2 22 45 2 17 38 2 12 36 2 18 43 2 13 44 2 41 13 2 26 9 2 8 22 2 35 17 2 36 40 2 19 4 2 7 6 2 48 39 2 30 19 2 42 27 2 10 3 2 45 5 2 15 12 2 46 47 2 27 23 2 9 2 2 21 24 2 23 33 2 32 28 2 44 8 2 16 21 2 25 48 2 37 31 2 15 39 2 29 1 2 1 25 2 24 34 2 33 41 2 47 10 2 4 11 2 38 29 2 3 37 2 ...
output:
Accepted: #move = 578
result:
ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 27504kb
input:
50 3 50 4 29 27 18 36 4 8 35 32 37 4 16 50 11 30 4 26 12 22 19 4 45 14 44 10 4 49 43 34 17 4 9 24 33 28 4 32 2 37 13 4 35 33 28 7 4 45 14 44 5 4 16 50 3 30 4 4 29 22 19 4 27 18 36 8 4 44 5 10 25 4 40 21 48 46 4 24 11 3 30 4 49 43 6 34 4 1 13 27 36 4 4 29 12 22 4 42 47 38 41 4 15 48 46 49 4 4 29 12 1...
output:
Accepted: #move = 1302
result:
ok
Test #27:
score: 0
Accepted
time: 4ms
memory: 27604kb
input:
50 3 50 4 47 3 4 5 4 5 4 6 3 4 2 4 5 1 4 1 5 2 3 4 4 1 2 3 4 2 8 10 11 4 9 12 11 8 4 10 9 6 7 4 11 10 8 7 4 9 11 8 6 4 7 6 10 9 4 14 17 7 16 4 22 17 14 15 4 13 12 15 16 4 13 16 14 17 4 12 14 15 17 4 12 15 13 16 4 20 21 26 19 4 20 22 18 21 4 22 19 18 21 4 19 18 20 22 4 21 19 20 13 4 25 27 28 24 4 25 ...
output:
Accepted: #move = 1302
result:
ok
Test #28:
score: 0
Accepted
time: 1ms
memory: 27576kb
input:
50 3 50 4 3 2 4 5 4 5 3 46 1 4 2 5 1 4 4 1 11 5 3 4 3 1 4 2 4 7 16 10 8 4 8 6 9 11 4 6 10 7 9 4 11 8 7 10 4 6 8 11 9 4 10 4 7 9 4 17 18 14 13 4 12 18 14 15 4 16 15 13 12 4 13 16 14 17 4 14 15 18 6 4 21 18 12 15 4 12 16 17 13 4 22 23 20 21 4 21 19 23 22 4 22 20 17 19 4 23 21 20 19 4 24 19 22 20 4 25 ...
output:
Accepted: #move = 1302
result:
ok
Test #29:
score: 0
Accepted
time: 4ms
memory: 27640kb
input:
50 3 50 4 2 10 3 9 4 1 4 10 3 4 5 1 2 4 4 3 2 50 6 4 3 7 6 13 4 8 7 5 4 4 6 8 9 5 4 9 6 7 10 4 10 7 8 1 4 1 8 9 2 4 12 13 16 17 4 14 11 13 17 4 5 15 12 11 4 21 15 12 16 4 17 16 13 14 4 11 17 15 14 4 15 16 11 12 4 20 19 22 21 4 21 18 22 20 4 21 22 18 19 4 14 18 20 19 4 24 18 19 20 4 24 25 26 27 4 23 ...
output:
Accepted: #move = 1302
result:
ok
Test #30:
score: 0
Accepted
time: 8ms
memory: 27568kb
input:
50 3 50 4 29 2 30 3 4 30 4 1 3 4 5 4 1 2 4 5 3 6 2 4 3 4 7 6 4 5 4 8 7 4 9 6 5 8 4 6 9 10 7 4 11 10 8 7 4 9 11 12 8 4 12 10 9 13 4 13 14 11 10 4 14 15 12 11 4 15 12 13 16 4 16 14 13 17 4 18 15 17 14 4 16 15 18 19 4 17 19 20 16 4 21 20 18 17 4 18 22 19 21 4 45 23 20 19 4 20 34 24 23 4 24 21 22 25 4 2...
output:
Accepted: #move = 1302
result:
ok
Subtask #3:
score: 0
Runtime Error
Test #31:
score: 0
Runtime Error
input:
200 3 200 6 149 79 143 164 179 68 4 44 52 144 113 1 84 3 31 188 166 1 109 4 154 192 125 147 1 198 4 103 27 192 95 3 33 166 179 1 125 3 31 61 150 3 168 152 161 2 67 64 1 136 2 150 17 1 192 2 15 142 2 56 122 1 35 2 97 200 2 129 22 4 72 134 31 21 2 53 82 4 195 181 104 146 1 78 1 88 3 8 78 127 4 152 200...
output:
Unauthorized output