/*
___ ___ ___ ___ ___ ___ ___ _____ ___ ___ ___
/ /\ /__/\ / /\ /__/\ / /\ /__/\ / /\ / /::\ / /\ / /\ / /\
/ /::\ | |::\ / /::\ \ \:\ / /::\ | |::\ / /::\ / /:/\:\ / /::\ / /::\ / /::\
/ /:/\:\ | |:|:\ / /:/\:\ \__\:\ / /:/\:\ | |:|:\ / /:/\:\ / /:/ \:\ / /:/\:\ / /:/\:\ / /:/\:\
/ /:/ \:\ __|__|:|\:\ / /:/ \:\ ___ / /::\ / /:/~/::\ __|__|:|\:\ / /:/~/::\ /__/:/ \__\:| / /:/ \:\ / /:/ \:\ / /:/ \:\
/__/:/ \__\:\ /__/::::| \:\ /__/:/ \__\:\ /__/\ /:/\:\ /__/:/ /:/\:\ /__/::::| \:\ /__/:/ /:/\:\ \ \:\ / /:/ /__/:/ \__\:\ /__/:/ \__\:\ /__/:/ \__\:\
\ \:\ / /:/ \ \:\~~\__\/ \ \:\ / /:/ \ \:\/:/__\/ \ \:\/:/__\/ \ \:\~~\__\/ \ \:\/:/__\/ \ \:\ /:/ \ \:\ / /:/ \ \:\ / /:/ \ \:\ / /:/
\ \:\ /:/ \ \:\ \ \:\ /:/ \ \::/ \ \::/ \ \:\ \ \::/ \ \:\/:/ \ \:\ /:/ \ \:\ /:/ \ \:\ /:/
\ \:\/:/ \ \:\ \ \:\/:/ \ \:\ \ \:\ \ \:\ \ \:\ \ \::/ \ \:\/:/ \ \:\/:/ \ \:\/:/
\ \::/ \ \:\ \ \::/ \ \:\ \ \:\ \ \:\ \ \:\ \__\/ \ \::/ \ \::/ \ \::/
\__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/
*/
#include <bits/stdc++.h>
#include "grader.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll >
#define F first
#define S second
#define ld long double
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;
const int MOD=1e9+7;
const int N=3e5+7;
long long po(ll x,ll y)
{
ll ans=1;
while(y){
if(y & 1) ans=(ans*x);//%MOD;
y/=2;
x=(x*x);//%MOD;
}
return ans;
}
vector<ll>v[N];
vector<ll>eul;
void dfs(ll x,ll p)
{
eul.pb(x);
for(ll i=0;i<v[x].size();i++){
if(v[x][i]!=p){
dfs(v[x][i],x);
}
}
}
int findEgg(int n, vector < pair < int, int > > edj)
{
for(ll i=0;i<edj.size();i++){
v[edj[i].F].pb(edj[i].S);
v[edj[i].S].pb(edj[i].F);
}
dfs(1,1);
set<int>s;
vector<int>que;
ll l=0,r=eul.size()-1,mid;
while(l<r){
mid=(l+r)/2;
for(ll i=0;i<=mid;i++) s.insert(eul[i]);
for(set<int>::iterator it=s.begin();it!=s.end();it++){
que.pb(*it);
}
if(query(que)) r=mid;
else l=mid+1;
s.clear();
que.clear();
}
for(ll i=1;i<=n;i++) v[i].clear();
eul.clear();
return eul[l];
}
void solve()
{
vector<pair<int,int> >edj;
edj.pb({1,2});
edj.pb({1,3});
edj.pb({2,4});
edj.pb({2,5});
edj.pb({4,8});
edj.pb({4,9});
edj.pb({4,10});
edj.pb({3,6});
edj.pb({3,7});
cout<<findEgg(10,edj);
}
/*
int main()
{
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen(".in","r",stdin);freopen("timeline.out","w",stdout);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
*/
Compilation message
eastereggs.cpp: In function 'void dfs(long long int, long long int)':
eastereggs.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(ll i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:63:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(ll i=0;i<edj.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7240 KB |
Number of queries: 4 |
| 2 |
Correct |
6 ms |
7240 KB |
Number of queries: 4 |
| 3 |
Correct |
6 ms |
7240 KB |
Number of queries: 4 |
| 4 |
Correct |
5 ms |
7240 KB |
Number of queries: 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7368 KB |
Number of queries: 8 |
| 2 |
Correct |
21 ms |
7404 KB |
Number of queries: 9 |
| 3 |
Correct |
34 ms |
7404 KB |
Number of queries: 9 |
| 4 |
Correct |
30 ms |
7368 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
7412 KB |
Number of queries: 9 |
| 2 |
Correct |
41 ms |
7392 KB |
Number of queries: 9 |
| 3 |
Correct |
35 ms |
7368 KB |
Number of queries: 9 |
| 4 |
Correct |
30 ms |
7516 KB |
Number of queries: 9 |
