oj.uz

Submission #977905

# Submission time Handle Problem Language Result Execution time Memory
977905 2024-05-08T13:33:02 Z AlphaMale06 Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 17 ms 1112 KB 
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define pb push_back


const int M = 513;
vector<int> g[M];
vector<int> qry;
vector<int> nwnodes;

bool mark[M];
int cnt=0;
int query(vector<int> h);

void dfs(int v, int p){
    if(cnt==0)return;
    if(!mark[v])cnt--;
    qry.push_back(v);
    if(!mark[v])nwnodes.pb(v);
    mark[v]=1;
    for(int to : g[v]){
        if(to!=p)dfs(to, v);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for(int i=1; i<=N; i++)g[i].clear();
    qry.clear();
    nwnodes.clear();
    for(int i=1; i<=N; i++)mark[i]=0;
    for(auto p : bridges){
        g[p.F].pb(p.S);
        g[p.S].pb(p.F);
    }
    if(N==1)return 1;
    int rest = N;
    for(int i=1; i<=9; i++){
        cnt = rest>>1;
        dfs(1, 1);
        int res = query(qry);
        if(res==1){
            for(int i=1; i<=N; i++)mark[i]=1;
            for(int e : nwnodes)mark[e]=0;
        }
        else{
            for(int e : qry)mark[e]=1;
        }
        nwnodes.clear();
        qry.clear();
        int cntm=0;
        for(int i=1; i<=N; i++){
            if(!mark[i])cntm++;
        }
        rest=cntm;
        if(cntm==1){
            for(int i=1; i<=N; i++){
                if(!mark[i])return i;
            }
        }
    }
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Number of queries: 8
2 Correct 10 ms 1112 KB Number of queries: 9
3 Correct 17 ms 988 KB Number of queries: 9
4 Correct 12 ms 732 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Number of queries: 9
2 Correct 11 ms 996 KB Number of queries: 9
3 Correct 13 ms 984 KB Number of queries: 9
4 Correct 13 ms 744 KB Number of queries: 9