oj.uz

Submission #261828

# Submission time Handle Problem Language Result Execution time Memory
261828 2020-08-12T05:47:12 Z kshitij_sodani Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 400 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "grader.h"

using namespace std;
vector<int> adj[520];
int vis[520];
pair<int,int> cur={-1,-1};
int xt;
int ss[520];
vector<int> kk;
int sol[520];
int le=0;
bool check(int x){
	return max(sol[x],sol[xt-x])<=le-1;
}
void dfs(int no,int par=-1){
	ss[no]=1;
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		dfs(j,no);
		ss[no]+=ss[j];
	}

	for(auto j:adj[no]){
		int val2=xt-ss[j];
		if(j==par){
			continue;
		}
		if(check(val2)){
			cur={no,j};
		}
	}
	if(check(ss[no])){
		cur={no,par};
	}
}
void dfs2(int no,int par=-1){
	kk.pb(no);
	vis[no]=1;
	for(auto j:adj[no]){
		if(j==par or j==cur.b){
			continue;
		}
		dfs2(j,no);
	}

}
int solve(int nn,vector<pair<int,int>> ed,vector<int> val){
	if(nn==1){
		return val[0];
	}
	for(auto j:val){
		adj[j].clear();
		vis[j]=0;
	}
	for(auto j:ed){
		adj[j.a].pb(j.b);
		adj[j.b].pb(j.a);
	}
	xt=nn;
	cur={-1,-1};
	dfs(val[0]);
	if(cur.a==-1){
		while(true){
			continue;
		}
	}
	kk.clear();
	dfs2(cur.a);
	le--;
	if(query(kk)){
		vector<pair<int,int>> ed2;
		for(auto j:ed){
			if(vis[j.a]==0 or vis[j.b]==0){
				continue;
			}
			ed2.pb(j);
		}
		return solve(kk.size(),ed2,kk);
	}
	else{
		vector<pair<int,int>> ed2;
		for(auto j:ed){
			if(vis[j.a]==1 or vis[j.b]==1){
				continue;
			}
			ed2.pb(j);
		}
		vector<int> ll;
		for(auto j:val){
			if(vis[j]==0){
				ll.pb(j);
			}
		}
		return solve(ll.size(),ed2,ll);
	}
}
int findEgg (int n, vector <pair <int,int>> ed){
    for(int i=2;i<=n;i++){
    	sol[i]=sol[(i+1)/2]+1;
    }
    
    for(int i=1;i<=9;i++){
    	if((1<<i)>=n){
    		le=i;
    		break;
    	}
    }
    if(n==1){
    	return 1;
    }
    vector<int> no;
    for(int i=1;i<=n;i++){
    	no.pb(i);
    }
    int ans=solve(n,ed,no);
  //  cout<<ans<<endl;
    return ans;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Number of queries: 4
2 Execution timed out 3046 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Number of queries: 8
2 Execution timed out 3065 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Number of queries: 9
2 Execution timed out 3090 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -