oj.uz

Submission #385750

# Submission time Handle Problem Language Result Execution time Memory
385750 2021-04-04T21:17:46 Z Iwanttobreakfree Easter Eggs (info1cup17_eastereggs) C++17
26.4 / 100
 63 ms 1684 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;
    vector<set<int> > cone(10000,set<int>());
    for(int i=0;i<N-1;i++){
        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(10000,true);
    cont=N;
    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(10000,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:48:14: warning: unused variable 'enco' [-Wunused-variable]
   48 |         bool enco=false;
      |              ^~~~

Subtask #1
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 788 KB Number of queries: 6
2 Partially correct 4 ms 788 KB Number of queries: 8
3 Partially correct 3 ms 788 KB Number of queries: 7
4 Partially correct 4 ms 788 KB Number of queries: 9

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 916 KB Number of queries: 13
2 Partially correct 34 ms 1004 KB Number of queries: 15
3 Partially correct 63 ms 916 KB Number of queries: 25
4 Runtime error 4 ms 1644 KB Execution killed with signal 6

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 916 KB Number of queries: 16
2 Runtime error 7 ms 1684 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -