oj.uz

Submission #385718

# Submission time Handle Problem Language Result Execution time Memory
385718 2021-04-04T19:33:41 Z Iwanttobreakfree Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 2 ms 364 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> c;
void conexa(vector<vector<int> >& cone,int raiz,int cont,vector<bool>& visto){
    c.push_back(raiz);
    visto[raiz]=true;
    for(int x: cone[raiz]){
        if(c.size()==cont){
            return;
        }
        if(!visto[x]){
            conexa(cone,x,cont,visto);
        }
    }
}
int findEgg (int N, vector < pair < int, int > > bridges){
    vector<vector<int> > cone(513,vector<int>());
    for(int i=0;i<N-1;i++){
        cone[bridges[i].first].push_back(bridges[i].second);
        cone[bridges[i].second].push_back(bridges[i].first);
    }
    int raiz,sol=0;
    vector<int> lista(N);
    vector<bool> visto(513,false);
    conexa(cone,bridges[0].first,N,visto);
    lista=c;
    //for(int i=0;i<lista.size();i++)cout<<lista[i]<<' ';
    vector<bool> posi(513,true);
    int cont=N/2;
    while(cont>0){
        c.clear();
        for(int i=0;i<N;i++){
            if(posi[lista[i]]){
                raiz=lista[i];
                break;
            }
        }
        vector<bool> visto(513,false);
        conexa(cone,raiz,cont,visto);
        if(true){
            set<int> s;
            for(int i=0;i<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];
            cone[c[0]].clear();
            posi[c[0]]=false;
            cont/=2;
        }
        else {
            for(int i=0;i<c.size();i++)posi[c[i]]=false;
        }
    }
    return sol;
}

Compilation message

eastereggs.cpp: In function 'void conexa(std::vector<std::vector<int> >&, int, int, std::vector<bool>&)':
eastereggs.cpp:9:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |         if(c.size()==cont){
      |            ~~~~~~~~^~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i=0;i<c.size();i++)s.insert(c[i]);
      |                         ~^~~~~~~~~
eastereggs.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int i=0;i<c.size();i++)posi[c[i]]=false;
      |                         ~^~~~~~~~~
eastereggs.cpp:40:15: warning: 'raiz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |         conexa(cone,raiz,cont,visto);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 364 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 364 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -