oj.uz

Submission #687440

# Submission time Handle Problem Language Result Execution time Memory
687440 2023-01-26T12:03:12 Z alexdd Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 193 ms 596 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
int n;
vector<int> con[520];
vector<int> forniv[520];
int level[520];
bool visited[520];
int parent[520];
int rez=-1;
int mxmniv=0;
int root;
int cntq;
map<vector<int>,int> done;
bool fa_query(vector<int> cv)
{
    if(done[cv]==0)
    {
        cntq--;
        bool bl = query(cv);
        if(bl==0)
            done[cv]=-1;
        else
            done[cv]=1;
    }
    if(done[cv]==-1)
        return 0;
    return 1;
}
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);
        }
    }
}
vector<int> aux;

int pls=1;
void dfs3(int nod, int dist)
{
    pls=max(pls,dist);
    visited[nod]=1;
    for(auto adj:con[nod])
    {
        if(!visited[adj])
            dfs3(adj,dist+1);
    }
}
int find_root()
{
    int mnm=n+2,care=1;
    for(int i=1;i<=n;i++)
    {
        for(int i=1;i<=n;i++)
            visited[i]=0;
        pls=1;
        dfs3(i,1);
        if(pls<mnm)
        {
            mnm=pls;
            care=i;
        }
    }
    return care;
}

vector<int> bfsorder;
void bfs()
{
    deque<int> dq;
    dq.push_back(root);
    while(!dq.empty())
    {
        int nod = dq.front();
        dq.pop_front();
        visited[nod]=1;
        bfsorder.push_back(nod);
        for(auto adj:con[nod])
            if(!visited[adj])
                dq.push_back(adj);
    }
}

int fr[520];
bool verif3(int poz)
{
    aux.clear();
    for(int i=0;i<=poz;i++)
        aux.push_back(bfsorder[i]);
    return fa_query(aux);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    n=N;
    if(n<=16)
        cntq = 4;
    else if(n<=500)
        cntq = 9;
    else
        cntq = 9;
    done.clear();
    for(int i=1;i<=N;i++)
    {
        visited[i]=0;
        con[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);
    }
    root = find_root();
    level[root] = 1;
    parent[root] = -1;
    for(int i=1;i<=n;i++)
        visited[i]=0;
    dfs(root);
    for(int i=1;i<=n;i++)
        visited[i]=0;
    bfs();
    int st,dr,mij=0;
    st=0;
    dr=n-1;
    while(st<=dr)
    {
        if(st==dr)
            return bfsorder[st];
        mij=(st+dr)/2;
        if(verif3(mij))
            dr=mij;
        else
            st=mij+1;
    }
    return bfsorder[mij];
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Correct 1 ms 208 KB Number of queries: 4
3 Correct 1 ms 208 KB Number of queries: 4
4 Correct 1 ms 332 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 436 KB Number of queries: 8
2 Correct 64 ms 500 KB Number of queries: 9
3 Correct 156 ms 572 KB Number of queries: 9
4 Correct 102 ms 552 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 584 KB Number of queries: 9
2 Correct 129 ms 540 KB Number of queries: 9
3 Correct 134 ms 596 KB Number of queries: 9
4 Correct 107 ms 520 KB Number of queries: 9