oj.uz

Submission #95279

# Submission time Handle Problem Language Result Execution time Memory
95279 2019-01-29T13:52:52 Z jangwonyoung Park (JOI17_park) C++14
100 / 100
 482 ms 888 KB 
#include "park.h"
#include<iostream>
#include<queue>
using namespace std;
#define pb push_back
//const int N=1401,M=1501;
int n;
vector<int>qry;
//int qar[1501];
vector<int>adj[1501];

vector<int>ds[1501];
int d[1501];
bool in[1501];
int tzuyu(int s,int e){
	int qar[n];
	for(int i=0; i<n ;i++) qar[i]=0;
	for(auto cur:qry) qar[cur]=1;
	if(s>e) swap(s,e);
	int res=Ask(s,e,qar);
	qry.clear();qry.shrink_to_fit();
	return res;
}
void add(int x,int y){
	adj[x].pb(y);adj[y].pb(x);
	Answer(min(x,y),max(x,y));
}
vector<int>g;vector<int>h;
bool vis[1501];
int bs(int s,int e){
	if(h.size()>1){
		for(auto cur:h) qry.pb(cur);
		int ret=tzuyu(s,e);
		if(ret){
			g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
			return -1;
		}
	}
	int l=0,r=g.size()-(h.size()!=1);
	while(l!=r){
		int mid=(l+r)/2;
		for(auto cur:h) qry.pb(cur);
		for(int i=0; i<=mid ;i++) qry.pb(g[i]);
		int res=tzuyu(s,e);
		if(res) r=mid;
		else l=mid+1;
	}
	if(l==g.size()){
		g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
		return -1;
	}
	int res=g[l];
	g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
	return res;
}
vector<int>v;
void expand(int x){
	in[x]=true;
	for(int i=0; i<n ;i++) if(in[i]) h.pb(i);
	for(int i=0; i<n ;i++) if(!in[i]) g.pb(i);
	int res=bs(0,x);
	in[res]=true;
	if(res==-1){
		v.push_back(x);
		return;
	}
	expand(res);
	expand(x);
}
bool vis2[1501];
void dfs(int id){
	g.push_back(id);
	vis2[id]=true;
	for(auto cur:adj[id]){
		if(in[cur] && !vis[cur] && !vis2[cur]) dfs(cur);
	}
}
void explode(int id,int x){
	for(int i=0; i<n ;i++) vis2[i]=false;
	h.pb(id);
	dfs(x);
	int res=bs(id,x);
	if(res==-1) return;
	add(res,id);
	vis[res]=true;
	for(auto cur:adj[res]){
		if(in[cur] && !vis[cur]) explode(id,cur);
	}
}
void addnode(int id){
	for(int i=0; i<n ;i++) vis[i]=!in[i];
	v.clear();
	expand(id);
	for(int i=1; i<v.size() ;i++) add(v[i-1],v[i]);
	for(int i=0; i<v.size() ;i++) in[v[i]]=false;
	explode(v[0],0);
	for(int i=0; i<v.size() ;i++) in[v[i]]=true;
}
void Detect(int T, int N){
	n=N;
	in[0]=true;
	for(int i=1; i<n ;i++){
		if(!in[i]) addnode(i);
	}
}

Compilation message

park.cpp: In function 'int bs(int, int)':
park.cpp:48:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l==g.size()){
     ~^~~~~~~~~~
park.cpp: In function 'void addnode(int)':
park.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<v.size() ;i++) add(v[i-1],v[i]);
               ~^~~~~~~~~
park.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size() ;i++) in[v[i]]=false;
               ~^~~~~~~~~
park.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size() ;i++) in[v[i]]=true;
               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 13 ms 380 KB Output is correct
4 Correct 53 ms 632 KB Output is correct
5 Correct 176 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 632 KB Output is correct
2 Correct 272 ms 624 KB Output is correct
3 Correct 239 ms 604 KB Output is correct
4 Correct 232 ms 676 KB Output is correct
5 Correct 236 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 604 KB Output is correct
2 Correct 309 ms 632 KB Output is correct
3 Correct 313 ms 632 KB Output is correct
4 Correct 281 ms 500 KB Output is correct
5 Correct 322 ms 504 KB Output is correct
6 Correct 299 ms 632 KB Output is correct
7 Correct 297 ms 760 KB Output is correct
8 Correct 306 ms 732 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 504 KB Output is correct
2 Correct 335 ms 716 KB Output is correct
3 Correct 328 ms 736 KB Output is correct
4 Correct 276 ms 504 KB Output is correct
5 Correct 311 ms 888 KB Output is correct
6 Correct 294 ms 760 KB Output is correct
7 Correct 255 ms 604 KB Output is correct
8 Correct 347 ms 776 KB Output is correct
9 Correct 285 ms 628 KB Output is correct
10 Correct 313 ms 788 KB Output is correct
11 Correct 316 ms 760 KB Output is correct
12 Correct 307 ms 632 KB Output is correct
13 Correct 265 ms 604 KB Output is correct
14 Correct 319 ms 632 KB Output is correct
15 Correct 260 ms 504 KB Output is correct
16 Correct 310 ms 632 KB Output is correct
17 Correct 235 ms 760 KB Output is correct
18 Correct 329 ms 648 KB Output is correct
19 Correct 277 ms 712 KB Output is correct
20 Correct 303 ms 636 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 760 KB Output is correct
2 Correct 439 ms 752 KB Output is correct
3 Correct 373 ms 592 KB Output is correct
4 Correct 337 ms 760 KB Output is correct
5 Correct 482 ms 616 KB Output is correct
6 Correct 256 ms 860 KB Output is correct
7 Correct 411 ms 744 KB Output is correct
8 Correct 333 ms 760 KB Output is correct
9 Correct 325 ms 760 KB Output is correct
10 Correct 350 ms 660 KB Output is correct
11 Correct 318 ms 632 KB Output is correct
12 Correct 349 ms 632 KB Output is correct
13 Correct 316 ms 660 KB Output is correct
14 Correct 459 ms 632 KB Output is correct
15 Correct 365 ms 764 KB Output is correct
16 Correct 300 ms 504 KB Output is correct
17 Correct 233 ms 632 KB Output is correct
18 Correct 316 ms 644 KB Output is correct