oj.uz

Submission #687331

# Submission time Handle Problem Language Result Execution time Memory
687331 2023-01-26T10:08:04 Z alexdd Easter Eggs (info1cup17_eastereggs) C++17
71.6 / 100
 53 ms 1076 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
int n;
vector<int> con[520];
vector<int> children[520];
vector<int> forniv[520];
int level[520];
bool visited[520];
int parent[520];
int rez=-1;
int mxmniv=0;
void dfs(int nod)
{
    visited[nod]=1;
    mxmniv = max(mxmniv, level[nod]);
    forniv[level[nod]].push_back(nod);
    for(auto adj:con[nod])
    {
        if(!visited[adj])
        {
            level[adj] = level[nod]+1;
            parent[adj]=nod;
            dfs(adj);
            for(int i=0;i<children[adj].size();i++)
                children[nod].push_back(children[adj][i]);
        }
    }
    children[nod].push_back(nod);
}
vector<int> aux;
void dfs2(int nod, int niv)
{
    visited[nod]=1;
    aux.push_back(nod);
    for(auto adj:con[nod])
    {
        if(!visited[adj] && level[adj]<=niv)
        {
            dfs2(adj, niv);
        }
    }
}

bool verif_nivel(int niv)
{
    for(int i=1;i<=n;i++)
        visited[i]=0;
    aux.clear();
    dfs2(1,niv);
    return query(aux);
}

int find_nivel()
{
    int st,dr,mij;
    st=1;
    dr=mxmniv;
    while(st<=dr)
    {
        if(st==dr)
            return st;
        mij=(st+dr)/2;
        if(verif_nivel(mij))
            dr=mij;
        else
            st=mij+1;
    }
    return mij;
}

int fr[520];
bool verif_interval(int le, int ri, int niv)///returneaza 1 daca oul se afla in nodurile de pe forniv[niv][le..ri]
{
    aux.clear();
    for(int i=1;i<=n;i++)
        fr[i]=0;
    for(int i=le;i<=ri;i++)
    {
        int cur=forniv[niv][i];
        while(cur!=-1)
        {
            fr[cur]++;
            cur = parent[cur];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fr[i]>0)
            aux.push_back(i);
    }
    return query(aux);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    n=N;
    for(int i=1;i<=N;i++)
    {
        visited[i]=0;
        con[i].clear();
        children[i].clear();
        forniv[i].clear();
    }
    rez=-1;
    mxmniv=0;
    for(auto x:bridges)
    {
        con[x.first].push_back(x.second);
        con[x.second].push_back(x.first);
    }
    level[1] = 1;
    parent[1]=-1;
    dfs(1);

    int niv = find_nivel();

    int st,dr,mij=0;
    st=0;
    dr=forniv[niv].size()-1;
    while(st<=dr)
    {
        if(st==dr)
            return forniv[niv][st];
        mij=(st+dr)/2;
        if(verif_interval(st,mij,niv))
            dr=mij;
        else
            st=mij+1;
    }
    return forniv[niv][mij];
}

Compilation message

eastereggs.cpp: In function 'void dfs(int)':
eastereggs.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int i=0;i<children[adj].size();i++)
      |                         ~^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int find_nivel()':
eastereggs.cpp:57:15: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     int st,dr,mij;
      |               ^~~

Subtask #1
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Number of queries: 5
2 Partially correct 1 ms 336 KB Number of queries: 6
3 Partially correct 1 ms 336 KB Number of queries: 6
4 Partially correct 1 ms 336 KB Number of queries: 5

Subtask #2
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 464 KB Number of queries: 9
2 Partially correct 9 ms 336 KB Number of queries: 11
3 Partially correct 20 ms 580 KB Number of queries: 12
4 Partially correct 12 ms 336 KB Number of queries: 12

Subtask #3
13.2 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 1076 KB Number of queries: 10
2 Partially correct 13 ms 336 KB Number of queries: 12
3 Partially correct 18 ms 336 KB Number of queries: 11
4 Partially correct 13 ms 336 KB Number of queries: 12