oj.uz

Submission #120549

# Submission time Handle Problem Language Result Execution time Memory
120549 2019-06-24T20:38:43 Z shayan_p Park (JOI17_park) C++14
100 / 100
 356 ms 784 KB 
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include "park.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1600;

vector<int> v[maxn], start ,vec ,vec2;
bool bad[maxn], mark[maxn], done[maxn];
int n, arr[maxn], Cnt;

/*

void Answer(int a,int b){
    cout<<"Found "<<a<<" "<<b<<endl;
}

bool mark2[maxn];
vector<int>v2[maxn];

void dfs2(int u,int *arr){
    mark2[u]=1;
    for(int y:v2[u]){
	if(mark2[y]==0 && arr[y])
	    dfs2(y,arr);
    }
}
int Ask(int a,int b,int *arr){
    assert( arr[a] && arr[b] );
    memset(mark2,0,sizeof mark2);
    dfs2(a,arr);
    return mark2[b];
}
*/
void _Answer(int a,int b){
    if(a>b) swap(a,b);
    return Answer(a,b);
}
int _Ask(int a,int b,int *arr){
    assert(a!=b && arr[a] && arr[b]);
    if(a>b) swap(a,b);
    return Ask(a,b,arr);		
}

void Dfs(int u){
    mark[u]=1;
    start.PB(u);
    for(int y:v[u]){
	if(mark[y]==0 && bad[y]==0)
	    Dfs(y);
    }
}
int Bs(int u){
    int l=-1,r=sz(start)-1;
    while(r-l > 1){
	int mid=(l+r)>>1;

	for(int i=0;i<n;i++)
	    arr[i]=0;
	for(int i=0;i<=mid;i++)
	    arr[ start[i] ]=1;
	arr[u]=1;
	
	if(_Ask(u,start[0],arr)) r=mid;
	else l=mid;
    }
    return start[r];
}
void Push(int u,int r){
    memset(mark,0,sizeof mark);
    start.clear(), Dfs(r);

    for(int i=0;i<n;i++)
	arr[i]=mark[i];
    arr[u]=arr[r]=1;
    if(_Ask(u,r,arr)==0) return;
    
    int w= Bs(u);
    _Answer(u,w), v[u].PB(w), v[w].PB(u), bad[w]=1;

    memset(mark,0,sizeof mark);
    
    vector<int>vec;
    
    for(int y:v[w]){
	if(mark[y]==0 && !bad[y]) vec.PB(y), Dfs(y);
    }
    for(int y:vec){
	Push(u,y);
    }
}
void Path(int u,int l=0,int r=sz(vec2)){
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=0;
    }
    if(_Ask(0,u,arr)) return;
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=1;
    }
    if(r-l==1) { vec.PB(vec2[l]); return; }
    int mid=(l+r)>>1;
    Path(u,l,mid), Path(u,mid,r);
}

void Detect(int _,int n){
    srand(time(0));
    ::n=n;
    
    done[0]=1, Cnt=1;
    
    while(Cnt<n){
	//	int id=rand()%(n-Cnt);
	int id=0;
	
	for(int i=0;i<n;i++){
	    if(done[i]) continue;
	    if(id==0){ id=i; break; }
	    id--;
	}
	
	memset(arr,0,sizeof arr);
	vec.clear(), vec2.clear();
	for(int i=0;i<n;i++){
	    arr[i]=1;
	    if(i!=id && !done[i]) vec2.PB(i);
	}
	vec.PB(id), Path(id);

	for(int i=0;i<n;i++){
	    arr[i]=0;
	}
	for(int x:vec){
	    arr[x]=1;
	}

	auto cmp=[&](int a,int b){
	    if(a==b) return false;
	    if(a==id) return false;
	    if(b==id) return true;
	    
	    arr[a]=0;
	    bool ans=_Ask(b,id,arr);
	    arr[a]=1;
	    return ans;
	};

	sort(vec.begin(), vec.end(), cmp);
	
	for(int x:vec){    
	    memset(bad,0,sizeof bad);
	    bad[x]=1;
	    Push(x,0);
	    done[x]=1;
	    Cnt++;
	}
    }
}
/*
int main(){
    int n,m; cin>>n>>m;
    while(m--){
	int a,b; cin>>a>>b;
	v2[a].PB(b), v2[b].PB(a);
    }
    Detect(-1,n);
    return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 19 ms 384 KB Output is correct
5 Correct 37 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 544 KB Output is correct
2 Correct 160 ms 632 KB Output is correct
3 Correct 155 ms 656 KB Output is correct
4 Correct 297 ms 632 KB Output is correct
5 Correct 277 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 784 KB Output is correct
2 Correct 222 ms 512 KB Output is correct
3 Correct 238 ms 644 KB Output is correct
4 Correct 198 ms 632 KB Output is correct
5 Correct 252 ms 512 KB Output is correct
6 Correct 224 ms 640 KB Output is correct
7 Correct 211 ms 632 KB Output is correct
8 Correct 228 ms 512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 504 KB Output is correct
2 Correct 272 ms 680 KB Output is correct
3 Correct 259 ms 512 KB Output is correct
4 Correct 229 ms 512 KB Output is correct
5 Correct 276 ms 512 KB Output is correct
6 Correct 222 ms 512 KB Output is correct
7 Correct 258 ms 668 KB Output is correct
8 Correct 238 ms 656 KB Output is correct
9 Correct 234 ms 596 KB Output is correct
10 Correct 261 ms 512 KB Output is correct
11 Correct 273 ms 632 KB Output is correct
12 Correct 246 ms 548 KB Output is correct
13 Correct 237 ms 512 KB Output is correct
14 Correct 248 ms 664 KB Output is correct
15 Correct 249 ms 632 KB Output is correct
16 Correct 237 ms 512 KB Output is correct
17 Correct 330 ms 572 KB Output is correct
18 Correct 255 ms 484 KB Output is correct
19 Correct 276 ms 624 KB Output is correct
20 Correct 242 ms 512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 780 KB Output is correct
2 Correct 351 ms 512 KB Output is correct
3 Correct 289 ms 632 KB Output is correct
4 Correct 260 ms 632 KB Output is correct
5 Correct 343 ms 652 KB Output is correct
6 Correct 252 ms 732 KB Output is correct
7 Correct 309 ms 664 KB Output is correct
8 Correct 263 ms 640 KB Output is correct
9 Correct 263 ms 632 KB Output is correct
10 Correct 259 ms 512 KB Output is correct
11 Correct 258 ms 632 KB Output is correct
12 Correct 302 ms 512 KB Output is correct
13 Correct 247 ms 636 KB Output is correct
14 Correct 356 ms 632 KB Output is correct
15 Correct 247 ms 632 KB Output is correct
16 Correct 239 ms 524 KB Output is correct
17 Correct 338 ms 632 KB Output is correct
18 Correct 212 ms 512 KB Output is correct