#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
using namespace std;
vector <int> v[100005];
int dp[100005],mx,l,f[100005],N,ANS;
priority_queue <pair<int,int> > pq;
void dfs(int x,int par){
dp[x] = dp[par] + 1;
for (int j=0;j<v[x].size();j++){
int to = v[x][j];
if (to == par) continue;
dfs(to,x);
}
if (dp[x] > mx)
mx = dp[x],l = x;
}
void clear(int n){
while(pq.size()) pq.pop();
for (int i = 1; i <= n; i++)
v[i].clear(),dp[i] = 0,f[i] = 0;
}
void go(int n, vector < pair < int, int > > vec,vector <int> vert){
if (vert.size() == 0) {
exit(0);
}
if (vert.size() == 1) {
ANS = vert[0];
return;
}
for (int i = 0; i < vec.size(); i++){
int a = vec[i].first,b = vec[i].second;
v[a].pb(b),v[b].pb(a);
}
mx = 1,l = vert[0];
dfs(vert[0],vert[0]);
vector <int> q; q.clear();
pq.push({mx,l});
while(pq.size()){
int x = pq.top().second;
pq.pop();
if (f[x] == 1) continue;
f[x] = 1,q.pb(x);
if (q.size() == (n+1)/2) break;
for (int j = 0; j<v[x].size(); j++){
int to = v[x][j];
if (!f[to]) pq.push({dp[to],to});
}
}
vector <pair<int,int> > edges; edges.clear();
vector <int> newv; newv.clear();
if (query(q) == 1){
for (int i=0;i<vec.size();i++){
int a = vec[i].first,b = vec[i].second;
if (f[a] && f[b]) edges.pb({a,b});
}
for (int i = 0; i < vert.size(); i++)
if (f[vert[i]]) newv.pb(vert[i]);
}
else{
for (int i=0;i<vec.size();i++){
int a = vec[i].first,b = vec[i].second;
if (!f[a] && !f[b]) edges.pb({a,b});
}
for (int i = 0; i < vert.size(); i++)
if (!f[vert[i]]) newv.pb(vert[i]);
}
clear(N);
go(newv.size(), edges, newv);
}
int findEgg (int n, vector < pair < int, int > > vec){
N = n,ANS=0;
vector <int> vert; vert.clear();
for (int i=1;i<=n;i++)
vert.pb(i);
go(n,vec,vert);
clear(N);
return ANS;
}
Compilation message
eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int j=0;j<v[x].size();j++){
| ~^~~~~~~~~~~~
eastereggs.cpp: In function 'void go(int, std::vector<std::pair<int, int> >, std::vector<int>)':
eastereggs.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
eastereggs.cpp:52:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | if (q.size() == (n+1)/2) break;
| ~~~~~~~~~^~~~~~~~~~
eastereggs.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int j = 0; j<v[x].size(); j++){
| ~^~~~~~~~~~~~
eastereggs.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i=0;i<vec.size();i++){
| ~^~~~~~~~~~~
eastereggs.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < vert.size(); i++)
| ~~^~~~~~~~~~~~~
eastereggs.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=0;i<vec.size();i++){
| ~^~~~~~~~~~~
eastereggs.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < vert.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2632 KB |
Number of queries: 4 |
| 2 |
Partially correct |
3 ms |
2660 KB |
Number of queries: 5 |
| 3 |
Partially correct |
2 ms |
2632 KB |
Number of queries: 5 |
| 4 |
Partially correct |
2 ms |
2652 KB |
Number of queries: 8 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
2632 KB |
Number of queries: 8 |
| 2 |
Partially correct |
9 ms |
2632 KB |
Number of queries: 16 |
| 3 |
Partially correct |
11 ms |
2728 KB |
Number of queries: 17 |
| 4 |
Runtime error |
4 ms |
5388 KB |
Execution killed with signal 6 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
2632 KB |
Number of queries: 9 |
| 2 |
Partially correct |
17 ms |
2632 KB |
Number of queries: 13 |
| 3 |
Partially correct |
15 ms |
2760 KB |
Number of queries: 18 |
| 4 |
Runtime error |
7 ms |
5516 KB |
Execution killed with signal 6 |
