Submission #386079

#	Time	Username	Problem	Language	Result	Execution time	Memory
386079		Iwanttobreakfree	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	18 ms	5148 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> c;
void conexa(vector<set<int> >& cone,int raiz,int cont,vector<bool>& visto){
    c.push_back(raiz);
    visto[raiz]=true;
    for(auto it=cone[raiz].begin();it!=cone[raiz].end();it++){
        if((int)c.size()==cont){
            return;
        }
        if(!visto[*it]){
            conexa(cone,*it,cont,visto);
        }
    }
}
int findEgg (int N, vector < pair < int, int > > bridges){
    set<int> se;
    int replace=1000;
    vector<set<int> > cone(100000,set<int>());
    for(int i=0;i<N-1;i++){
    	if(bridges[i].first<0){
    	bridges[i].first=replace;
		replace++;	
		}
		if(bridges[i].second<0){
    	bridges[i].first=replace;
		replace++;	
		}
        se.insert(bridges[i].first);
        se.insert(bridges[i].second);
        cone[bridges[i].first].insert(bridges[i].second);
        cone[bridges[i].second].insert(bridges[i].first);
    }
    int raiz,sol=0;
    vector<int> lista(N);
    int cont=0;
    for(auto it=se.begin();it!=se.end();it++){
        lista[cont]=*it;
        cont++;
    }
    vector<bool> posi(100000,true);
    cont=N/2;
    while(cont>0){
        c.clear();
        bool enc=false;
        for(int i=0;i<N;i++){
            if(posi[lista[i]]){
                raiz=lista[i];
                enc=true;
                break;
            }
        }
        if(!enc)break;
        vector<bool> visto(100000,false);
        conexa(cone,raiz,cont,visto);
        bool enco=false;
        if(query(c)){
            set<int> s;
            for(int i=0;i<(int)c.size();i++)s.insert(c[i]);
            for(int i=0;i<N;i++){
                if(s.find(lista[i])==s.end())posi[lista[i]]=false;
            }
            sol=c[c.size()/2];
            posi[sol]=false;
            for(auto it=cone[sol].begin();it!=cone[sol].end();it++){
                cone[*it].erase(c[0]);
            }
            cont/=2;
        }
        else {
            for(int i=0;i<(int)c.size();i++){
            	posi[c[i]]=false;
            	for(auto it=cone[c[i]].begin();it!=cone[c[i]].end();it++){
                cone[*it].erase(c[i]);
            }
        }
        cont/=2;
        }
    }
    return sol;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:57:14: warning: unused variable 'enco' [-Wunused-variable]
   57 |         bool enco=false;
      |              ^~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20