#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN=520;
vector<int> adj[MAXN];
bool cmarked[MAXN],dfsvisited[MAXN];
int sizes[MAXN];
vector<int> subtrees[MAXN];
void dfs(int node,int parent){
int sm=1;
subtrees[node].push_back(node);
for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
{
if(*it==parent||cmarked[*it] || dfsvisited[*it])continue;
dfs(*it,node);
sm+=sizes[*it];
}
sizes[node]=sm;
}
int noofchild[MAXN];
vector<int> reelchild[MAXN];
int tsa=0;
void subtreedfs(int node,int parent){
subtrees[node].push_back(node);
for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
{
if(*it==parent||cmarked[*it])continue;
reelchild[node].push_back(*it);
subtreedfs(*it,node);
noofchild[node]++;
for(vector<int>::iterator it2=subtrees[*it].begin();it2!=subtrees[*it].end();it2++){
subtrees[node].push_back(*it2);
}
}
}
int getcentroidhelper(int node,int parent,int sayi){
bool iscntr=true;
int heaviest=-1;
for (vector<int>::iterator it = adj[node].begin(); it!=adj[node].end() ; it++)
{
if(*it==parent || cmarked[*it])continue;
if(sizes[*it]>sayi/2)
iscntr=false;
if(heaviest==-1||sizes[*it]>sizes[heaviest])heaviest=*it;
}
int snc=0;
if(iscntr && sayi-sizes[node]<=sayi/2)
snc= node;
else snc= getcentroidhelper(heaviest,node,sayi);
cmarked[snc]=true;
return snc;
}
int getcentroid(int node){
dfs(node,-1);
if(sizes[node]<=2)return node;
int cikan= getcentroidhelper(node,-1,sizes[node]);
return cikan;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
for(int i=1;i<=N;i++){
subtrees[i].clear();
noofchild[i]=0;
reelchild[i].clear();
adj[i].clear();
cmarked[i]=false;
dfsvisited[i]=false;
sizes[i]=0;
}
for(int i=0;i<(int)bridges.size();i++){
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
/*
3
1 2
1 3
3
1
2
3
16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
* */
int nd=1;
/*
16
1 2
2 3
1 4
4 5
5 6
5 7
7 8
8 9
9 10
8 11
10 12
4 13
4 14
4 15
1 16
* */
while(true){
int centro=getcentroid(nd);
//cout << centro<<"\n";
for(int i=1;i<=N;i++){
subtrees[i].clear();
noofchild[i]=0;
reelchild[i].clear();
}
//cout <<"clear"<<"\n";
if(sizes[centro]==1)return centro;
vector<int> a;
a.push_back(centro);
if(query(a))return centro;
subtreedfs(centro,-1);
//if(sizes[centro]==2)return reelchild[centro][0];
for(int i=0;i<(int)reelchild[centro].size();i++){
//cout << reelchild[centro][i]<<" ";
}
//cout <<"\n";
int low=0,high=noofchild[centro]-1;
int mid=(low+high)/2;
int sol=-1;
while(low<=high){
mid=(low+high)/2;
vector<int> sorgula;
//cout << "low: "<<low<<" high: "<<high<<" mid: "<<mid<<"\n";
//cout << "sorguluyor: \n";
sorgula.push_back(centro);
/*if((low==noofchild[centro]-1 || high==0) && sol==-1){
sol= mid;
break;
}*/
for(int i=0;i<=mid;i++){
//cout << "child: "<<reelchild[centro][i]<<"\n";
for(int j=0;j<(int)subtrees[reelchild[centro][i]].size();j++){
sorgula.push_back(subtrees[reelchild[centro][i]][j]);
//cout << sorgula[sorgula.size()-1]<<" ";
}
//cout<<"\n";
}
if(query(sorgula)){
//cout << "sorgu doğru: "<<"\n";
high=mid-1;
sol=mid;
}
else{
//cout << "sorgu yanlış\n";
low=mid+1;
}
}
if(sol==-1)return centro;
nd=reelchild[centro][sol];
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Number of queries: 11 |
| 2 |
Incorrect |
3 ms |
436 KB |
Number of queries: 10 |
| 3 |
Incorrect |
5 ms |
436 KB |
Number of queries: 10 |
| 4 |
Incorrect |
3 ms |
464 KB |
Number of queries: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
572 KB |
Number of queries: 21 |
| 2 |
Incorrect |
35 ms |
572 KB |
Number of queries: 25 |
| 3 |
Incorrect |
49 ms |
572 KB |
Number of queries: 22 |
| 4 |
Runtime error |
33 ms |
820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
1144 KB |
Number of queries: 23 |
| 2 |
Incorrect |
36 ms |
1144 KB |
Number of queries: 25 |
| 3 |
Incorrect |
44 ms |
1144 KB |
Number of queries: 22 |
| 4 |
Incorrect |
57 ms |
1144 KB |
Number of queries: 45 |
