oj.uz

Submission #385753

# Submission time Handle Problem Language Result Execution time Memory
385753 2021-04-04T21:23:09 Z Iwanttobreakfree Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 400 ms 48080 KB 
#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(1000000,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(1000000,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(1000000,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[0];
            posi[c[0]]=false;
            for(auto it=cone[sol].begin();it!=cone[sol].end();it++){
                cone[*it].erase(c[0]);
            }
            cont=c.size()/2;
        }
        else {
            for(int i=0;i<(int)c.size();i++)posi[c[i]]=false;
        }
    }
    return sol;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 448 ms 47728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 717 ms 47892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1482 ms 48080 KB Time limit exceeded
2 Halted 0 ms 0 KB -