This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeon2.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 200;
const int INF = 1000;
vector<pii> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];
vector<int> to[MAX_N+1];
vector<int> s[MAX_N+1], e[MAX_N+1];
pii p[MAX_N+1];
int deg[MAX_N+1];
int N = 1;
bool chk[MAX_N+1];
void dfs1(int x){
//cout<<x<<endl;
deg[x] = NumberOfRoads();
for(int i=0; i<=deg[x]; i++){
to[x].pb(0);
s[x].pb(0); e[x].pb(0);
}
if(x!=1){
p[x].second = LastRoad();
to[x][p[x].second] = p[x].first;
}
for(int i=1; i<=deg[x]; i++){
if(to[x][i]==0){
Move(i, 2);
int c = Color();
int t = LastRoad();
if(c==1){
N++;
p[N].first = x;
gp2[x].pb(N);
gp2[N].pb(x);
to[x][i] = N;
dfs1(N);
Move(t, 3);
}else if(c==2){
to[x][i] = -1;
Move(t, 2);
}else{
to[x][i] = -2;
Move(t, 3);
}
}
}
}
void dfs2(int x){
//cout<<x<<endl;
for(int i=1; i<=deg[x]; i++){
if(to[x][i]==p[x].first) continue;
if(to[x][i]==-2) continue;
if(to[x][i]==-1){
Move(i, 1);
int c = Color();
if(c==2){
s[x][i] = (s[x][i]+e[x][i])/2+1;
}else{
e[x][i] = (s[x][i]+e[x][i])/2;
}
Move(LastRoad(), c);
if(s[x][i]==e[x][i]){
gp2[x].pb(s[x][i]);
gp2[s[x][i]].pb(x);
to[x][i] = -2;
}
}else{
if(chk[x]){
Move(i, 3);
dfs2(to[x][i]);
Move(p[to[x][i]].second, 1);
}else{
Move(i, 2);
dfs2(to[x][i]);
Move(p[to[x][i]].second, 1);
}
}
}
}
vector<pii> v1, v2;
int dist[MAX_N+1];
int ans[MAX_N+1];
deque<int> dq;
void bfs(int x){
dq.pb(x);
dist[x] = 0;
while(!dq.empty()){
int now = dq.front(); dq.pop_front();
for(int i : gp2[now]){
if(dist[i]>dist[now]+1){
dist[i] = dist[now]+1;
dq.pb(i);
}
}
}
}
void Inspect(int R){
dfs1(1);
v1.pb({1, N});
for(int i=1; i<=N; i++){
for(int j=1; j<=deg[i]; j++){
if(to[i][j]==-1){
s[i][j] = 1;
e[i][j] = N;
}
}
}
while(!v1.empty()){
for(pii p : v1){
if(p.first!=p.second){
v2.pb({p.first, (p.first+p.second)/2});
v2.pb({(p.first+p.second)/2+1, p.second});
}
}
while(!v1.empty()) v1.pop_back();
for(pii p : v2){
v1.pb(p);
}
while(!v2.empty()) v2.pop_back();
for(int i=1; i<=N; i++){
chk[i] = false;
}
if(v1.empty()) break;
for(int i=0; i<v1.size(); i+=2){
pii p = v1[i];
for(int j=p.first; j<=p.second; j++){
chk[j] = true;
}
}
dfs2(1);
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
dist[j] = INF;
}
bfs(i);
//cout<<i<<endl;
for(int j=1; j<=N; j++){
//cout<<j<<" "<<dist[j]<<endl;
if(dist[j]!=0){
ans[dist[j]]++;
}
}
}
for(int i=1; i<=R; i++){
//cout<<i<<" "<<ans[i]<<endl;
if(R<=N){
Answer(i, ans[i]/2);
}else{
Answer(i, 0);
}
}
}
Compilation message (stderr)
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:140:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v1.size(); i+=2){
~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |