oj.uz

Submission #80824

# Submission time Handle Problem Language Result Execution time Memory
80824 2018-10-22T12:33:21 Z farukkastamonuda Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 3 ms 804 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 530
#define mp make_pair
#define pb push_back
using namespace std;
int cur,mark[li], now;
vector<int> v[li], send;
void dfs(int node,int ata){
	if(now==cur/2) return ;
	now += (! mark[node]);
	send.pb(node);
	for(int i = 0;i < (int)v[node].size(); i++){
		int go = v[node][i];
		if(go != ata) dfs(go,node);
	}
}
int findEgg(int N, vector< pair<int, int> > bridges){
	for(int i = 0; i < N - 1; i++){
		int x = bridges[i].fi;
		int y = bridges[i].se;
		v[x].pb(y);
		v[y].pb(x);
	}
	cur = N;
	while(cur > 1){
		now = 0;
		dfs(1, 0);
		if(query(send) == 1){
			cur /= 2;
			for(int i = 1;i <= N ; i++){
				mark[i] = 1;
			}
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]] = 0;
			}
		}
		else{
			cur = cur - cur / 2;
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]]=1;
			}
		}
		send.clear();
	}
	for(int i = 1;i <= N; i++){
		if(mark[i] == 0) return i;
	}
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -