oj.uz

Submission #385754

# Submission time Handle Problem Language Result Execution time Memory
385754 2021-04-04T21:24:04 Z Iwanttobreakfree Easter Eggs (info1cup17_eastereggs) C++17
26.4 / 100
 83 ms 10300 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(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[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
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 5020 KB Number of queries: 6
2 Partially correct 20 ms 5020 KB Number of queries: 7
3 Partially correct 15 ms 5020 KB Number of queries: 7
4 Partially correct 17 ms 5120 KB Number of queries: 9

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 5148 KB Number of queries: 13
2 Partially correct 51 ms 5148 KB Number of queries: 17
3 Partially correct 82 ms 5148 KB Number of queries: 24
4 Runtime error 14 ms 10300 KB Execution killed with signal 6

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 69 ms 5296 KB Number of queries: 15
2 Partially correct 82 ms 5148 KB Number of queries: 44
3 Partially correct 83 ms 5148 KB Number of queries: 32
4 Runtime error 12 ms 10220 KB Execution killed with signal 6