oj.uz

답안 #95218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95218 2019-01-28T16:12:45 Z jangwonyoung Park (JOI17_park) C++14
67 / 100
 160 ms 832 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;
int bs(int s,int e){
	int l=0,r=g.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;
	}
	int res=g[l];
	g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
	return res;
}
void expand(int x,int y){
	qry.pb(x);qry.pb(y);
	if(tzuyu(x,y)){
		d[y]=d[x]+1;ds[d[y]].pb(y);
		add(x,y);
		return;
	}
	h.pb(x);h.pb(y);
	for(int i=0; i<n ;i++) if(!in[i]) g.pb(i);
	int res=bs(x,y);
	in[res]=true;
	expand(x,res);expand(res,y);
}
void addtotree(int id){
	for(int i=0; i<n ;i++) for(auto cur:ds[i]) g.pb(cur);//bfs order of some kind
	for(int i=0; i<n ;i++) if(!in[i]) h.pb(i);
	int boss=bs(0,id);in[id]=true;
	expand(boss,id);
}
void init(){
	ds[0].pb(0);
	in[0]=true;
}
void Detect(int T, int N){
	n=N;
	init();
	for(int i=1; i<n ;i++){
		if(!in[i]) addtotree(i);
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 632 KB Output is correct
2 Correct 155 ms 632 KB Output is correct
3 Correct 122 ms 664 KB Output is correct
4 Correct 60 ms 632 KB Output is correct
5 Correct 59 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 504 KB Output is correct
2 Correct 157 ms 604 KB Output is correct
3 Correct 158 ms 640 KB Output is correct
4 Correct 151 ms 644 KB Output is correct
5 Correct 152 ms 504 KB Output is correct
6 Correct 152 ms 632 KB Output is correct
7 Correct 156 ms 632 KB Output is correct
8 Correct 160 ms 504 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 544 KB Output is correct
2 Correct 129 ms 612 KB Output is correct
3 Correct 128 ms 832 KB Output is correct
4 Correct 106 ms 604 KB Output is correct
5 Correct 98 ms 632 KB Output is correct
6 Correct 113 ms 760 KB Output is correct
7 Correct 73 ms 636 KB Output is correct
8 Correct 120 ms 676 KB Output is correct
9 Correct 100 ms 500 KB Output is correct
10 Correct 126 ms 632 KB Output is correct
11 Correct 115 ms 764 KB Output is correct
12 Correct 125 ms 632 KB Output is correct
13 Correct 74 ms 612 KB Output is correct
14 Correct 132 ms 764 KB Output is correct
15 Correct 76 ms 632 KB Output is correct
16 Correct 157 ms 504 KB Output is correct
17 Correct 60 ms 636 KB Output is correct
18 Correct 127 ms 604 KB Output is correct
19 Correct 70 ms 680 KB Output is correct
20 Correct 108 ms 616 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 632 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -