oj.uz

Submission #261802

# Submission time Handle Problem Language Result Execution time Memory
261802 2020-08-12T05:29:54 Z kshitij_sodani Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 11 ms 640 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;
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(val2==(xt/2) or val2==(xt+1)/2){
			cur={no,j};
		}
	}
	if(ss[no]==xt/2 or ss[no]==(xt+1)/2){
		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);
	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){
    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 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 416 KB Number of queries: 8
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 384 KB Number of queries: 9
2 Runtime error 1 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -