oj.uz

Submission #61655

# Submission time Handle Problem Language Result Execution time Memory
61655 2018-07-26T09:13:47 Z minhcool Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 80 ms 55508 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
 
const int N = 1000000;
int ck[N], cur, num, cnt;
vector<int> Adjlist[N], check;
 
void dfs(int u, int p){
	if(cur == cnt) return;
	if(ck[u]){
		cur++;
	}
  	check.push_back(u);
	for(auto v: Adjlist[u]){
		if(v != p){
			dfs(v, u);
		}
	}
  return;
}
 
int findEgg(int N, vector<pair<int, int>> bridges){
	memset(ck, 1, sizeof ck);
	int n = N;
  	for (int i = 1 ;i <= n; ++i) Adjlist[i].clear();
	for(int i = 0; i < n - 1; i++){
		Adjlist[bridges[i].first].push_back(bridges[i].second);
		Adjlist[bridges[i].second].push_back(bridges[i].first);
	}
	num = n;
	while(num != 1){
		cnt = (num + 1) / 2;
		check.clear();
		cur = 0;
		dfs(1, 1);
		if(query(check)){
			for(int i = 1; i <= n; i++) ck[i] = 0;
			for(int i = 0; i < check.size(); i++) ck[check[i]] = 1;
			num = cnt;
		}
		else{
			for(int i = 0; i < check.size(); i++) ck[check[i]] = 0;
			num -= cnt;
		}
	}
	for(int i = 1; i <= n; i++) if(ck[i]) return i;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < check.size(); i++) ck[check[i]] = 1;
                   ~~^~~~~~~~~~~~~~
eastereggs.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < check.size(); i++) ck[check[i]] = 0;
                   ~~^~~~~~~~~~~~~~
eastereggs.cpp:48: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 54 ms 55204 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 62 ms 55460 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 80 ms 55508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -