oj.uz

Submission #588584

# Submission time Handle Problem Language Result Execution time Memory
588584 2022-07-03T15:14:25 Z Iwanttobreakfree Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 38 ms 400 KB 
#include <iostream>
#include <vector>
#include <set>
#include "grader.h"
using namespace std;
void dfs(int a,int par,vector<vector<int>>& g,vector<int>& pos,int& cnt,set<int>& q){
    if(cnt){
        q.insert(a);
        if(pos[a])cnt--;
    }else return;
    for(int x:g[a]){
        if(x==par)continue;
        dfs(x,a,g,pos,cnt,q);
        if(!cnt)return;
    }
}
int findEgg (int n,vector<pair<int,int>> bridges){
    vector<vector<int>> g(n+1,vector<int>());
    vector<int> pos(n+1,1);
    for(auto x:bridges){
        //x.first--;x.second--;
        g[x.first].push_back(x.second);
        g[x.second].push_back(x.first);
    }
    int l=1,r=n;
    while(l<r){
        int mid=(r+l)/2;
        set<int> s;
        dfs(1,1,g,pos,mid,s);
        vector<int> q;
        for(auto x:s)q.push_back(x);
        int egg=query(q);
        int y=0;
        for(int i=1;i<=n;i++){
            if(pos[i]){
                if(egg&&s.find(i)==s.end())pos[i]=0;
                if(!egg&&s.find(i)!=s.end())pos[i]=0;
            }
            if(pos[i])y++;
        }
        r=y;
    }
    for(int i=1;i<=n;i++)if(pos[i])return i;
    return -1;
}

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 208 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Number of queries: 8
2 Correct 20 ms 360 KB Number of queries: 9
3 Correct 36 ms 376 KB Number of queries: 9
4 Correct 28 ms 368 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 400 KB Number of queries: 9
2 Correct 27 ms 372 KB Number of queries: 9
3 Correct 34 ms 372 KB Number of queries: 9
4 Correct 38 ms 336 KB Number of queries: 9