oj.uz

Submission #191993

# Submission time Handle Problem Language Result Execution time Memory
191993 2020-01-15T04:48:48 Z dndhk None (JOI16_dungeon2) C++14
94 / 100
 32 ms 1940 KB 
#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(p[to[x][i]].second, 3);
			}else if(c==2){
				to[x][i] = -1;
				Move(LastRoad(), 2);
			}else{
				to[x][i] = -2;
				Move(LastRoad(), 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(i<=N){
			Answer(i, ans[i]/2);
		}else{
			Answer(i, 0);
		}
	}
}

Compilation message

dungeon2.cpp: In function 'void dfs1(int)':
dungeon2.cpp:39:8: warning: unused variable 't' [-Wunused-variable]
    int t = LastRoad();
        ^
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){
                ~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 580 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 1 ms 504 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 2 ms 504 KB Output is correct

Subtask #3
50.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 732 KB Partially correct
2 Partially correct 4 ms 760 KB Partially correct
3 Partially correct 6 ms 888 KB Partially correct
4 Partially correct 32 ms 1940 KB Partially correct
5 Partially correct 3 ms 504 KB Partially correct
6 Partially correct 3 ms 632 KB Partially correct
7 Partially correct 4 ms 760 KB Partially correct
8 Partially correct 4 ms 760 KB Partially correct
9 Partially correct 4 ms 888 KB Partially correct
10 Partially correct 4 ms 760 KB Partially correct
11 Partially correct 4 ms 888 KB Partially correct
12 Partially correct 4 ms 760 KB Partially correct
13 Partially correct 9 ms 1024 KB Partially correct
14 Partially correct 6 ms 760 KB Partially correct
15 Partially correct 4 ms 760 KB Partially correct
16 Partially correct 8 ms 760 KB Partially correct
17 Partially correct 28 ms 1784 KB Partially correct
18 Partially correct 26 ms 1784 KB Partially correct
19 Partially correct 28 ms 1912 KB Partially correct