oj.uz

Submission #261797

# Submission time Handle Problem Language Result Execution time Memory
261797 2020-08-12T05:22:35 Z kshitij_sodani Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 400 ms 512 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];
	}
	int su=xt;

	for(auto j:adj[no]){
		int val2=xt-ss[j];
		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);
    }
    return solve(n,ed,no);
}

Compilation message

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:27:6: warning: unused variable 'su' [-Wunused-variable]
  int su=xt;
      ^~

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 3068 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Number of queries: 8
2 Execution timed out 3077 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 12 ms 512 KB Number of queries: 9
2 Execution timed out 3072 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -