#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e9+100))
#define MOD ((ll)(1e9+7))
//void Inspect(int R);
//void Answer(int D, int A);
//void Move(int I, int V);
//int NumberOfRoads();
//int LastRoad();
//int Color();
#define num NumberOfRoads
#define lst LastRoad
#define clr Color
stack<ll> g;
vector<pair<ll,ll> > v[400];
ll C=1;
ll pr[400];
ll nm[400];
void mvb(){
ll t=g.top();
g.pop();
if(t>=0)Move(t,2);
}
ll n=0;
ll go(ll f){
g.push(LastRoad());
ll k=Color();
if(k==2){mvb(); return 0;}
n++;
ll x=n;
pr[x]=lst();
if(f)v[x].pb({f,pr[x]});
ll m=num();
nm[x]=m;
for(int i=1; i<=m; i++){
if(i==g.top())continue;
Move(i,2);
ll k=go(x);
if(k)v[x].pb({k,i});
}
mvb();
return x;
}
ll f[400][400];
ll ef[700][700];
ll dp[400][400];
ll bk[400][400];
ll pw[400];
ll pas[400];
ll cr;
ll gc(ll x){
return (x/pw[cr])%3+1;
}
ll gcc(ll x){
return (x/pw[cr+1])%3+1;
}
vector<ll> ord;
ll out[400];
//void dfs(ll x){
// for(auto y:v[x]){
// if(y.sc==pr[x])continue;
// Move(y.sc,gc(x));
// dfs(y.fr);
// }
// if(pr[x]>=0)
// Move(pr[x],gc(x));
//}
void slv(ll x){
for(auto y:v[x]){
if(y.sc==pr[x])continue;
Move(y.sc,gc(x));
slv(y.fr);
}
for(int i=1; i<=num(); i++){
if(ef[x][i])continue;
Move(i,clr());
f[x][i]+=(clr()-1)*pw[cr];
bk[x][i]=lst();
Move(lst(),clr());
}
if(pr[x]>=0)
Move(pr[x],gc(x));
}
void Inspect(int R) {
go(0);
for(int i=1; i<=n; i++){
for(auto x:v[i]){
ef[i][x.sc]=1;
f[i][x.sc]=x.fr;
}
}
pw[0]=1;
for(int i=1; i<15; i++)pw[i]=pw[i-1]*3;
// dfs(1);
for(cr=0; pw[cr]-1<n+1; cr++)
slv(1);
//reverse(ord.begin(),ord.end());
for(int i=1; i<=n; i++)
for(int j=1; j<=nm[i]; j++){
if(ef[i][j])continue;
f[f[i][j]][bk[i][j]]=i;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dp[i][j]=MAX;
for(int i=1; i<=n; i++)
for(int j=1; j<=nm[i]; j++)
dp[i][f[i][j]]=1;
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
pas[dp[i][j]]++;
for(int i = 1; i <= R; i++)
Answer(i, pas[i]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1016 KB |
Output is correct |
3 |
Correct |
5 ms |
1204 KB |
Output is correct |
4 |
Correct |
4 ms |
1204 KB |
Output is correct |
5 |
Correct |
3 ms |
1292 KB |
Output is correct |
6 |
Correct |
3 ms |
1292 KB |
Output is correct |
7 |
Correct |
3 ms |
1292 KB |
Output is correct |
8 |
Correct |
3 ms |
1292 KB |
Output is correct |
9 |
Correct |
3 ms |
1296 KB |
Output is correct |
10 |
Correct |
3 ms |
1424 KB |
Output is correct |
11 |
Correct |
3 ms |
1424 KB |
Output is correct |
12 |
Correct |
3 ms |
1424 KB |
Output is correct |
13 |
Correct |
3 ms |
1436 KB |
Output is correct |
14 |
Correct |
4 ms |
1436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1436 KB |
Output is correct |
2 |
Correct |
3 ms |
1436 KB |
Output is correct |
3 |
Correct |
4 ms |
1436 KB |
Output is correct |
4 |
Correct |
4 ms |
1436 KB |
Output is correct |
5 |
Correct |
3 ms |
1436 KB |
Output is correct |
6 |
Correct |
4 ms |
1436 KB |
Output is correct |
7 |
Correct |
3 ms |
1436 KB |
Output is correct |
8 |
Correct |
3 ms |
1436 KB |
Output is correct |
9 |
Correct |
3 ms |
1436 KB |
Output is correct |
10 |
Correct |
4 ms |
1436 KB |
Output is correct |
11 |
Correct |
3 ms |
1436 KB |
Output is correct |
12 |
Correct |
3 ms |
1436 KB |
Output is correct |
13 |
Correct |
3 ms |
1436 KB |
Output is correct |
14 |
Correct |
4 ms |
1436 KB |
Output is correct |
15 |
Correct |
4 ms |
1436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
3196 KB |
Output is correct |
2 |
Partially correct |
16 ms |
3452 KB |
Partially correct |
3 |
Partially correct |
16 ms |
3708 KB |
Partially correct |
4 |
Partially correct |
33 ms |
3816 KB |
Partially correct |
5 |
Partially correct |
3 ms |
3816 KB |
Partially correct |
6 |
Partially correct |
8 ms |
3816 KB |
Partially correct |
7 |
Partially correct |
23 ms |
3816 KB |
Partially correct |
8 |
Partially correct |
21 ms |
3816 KB |
Partially correct |
9 |
Partially correct |
17 ms |
3836 KB |
Partially correct |
10 |
Partially correct |
17 ms |
3836 KB |
Partially correct |
11 |
Partially correct |
19 ms |
3836 KB |
Partially correct |
12 |
Partially correct |
18 ms |
3836 KB |
Partially correct |
13 |
Partially correct |
20 ms |
3836 KB |
Partially correct |
14 |
Correct |
20 ms |
3836 KB |
Output is correct |
15 |
Partially correct |
17 ms |
3836 KB |
Partially correct |
16 |
Partially correct |
8 ms |
3836 KB |
Partially correct |
17 |
Partially correct |
43 ms |
3836 KB |
Partially correct |
18 |
Partially correct |
31 ms |
3836 KB |
Partially correct |
19 |
Partially correct |
30 ms |
3836 KB |
Partially correct |