oj.uz

Submission #958798

# Submission time Handle Problem Language Result Execution time Memory
958798 2024-04-06T17:39:57 Z LaviniaTornaghi Easter Eggs (info1cup17_eastereggs) C++17
26.4 / 100
 18 ms 532 KB 
#include<bits/stdc++.h>
using namespace std;

int query(vector<int> h);

int findEgg (int N, vector < pair < int, int > > bridges){
    vector<vector<int>> t(N+1);
    for(auto [a,b]:bridges){
        t[a].push_back(b);
        t[b].push_back(a);
    }
    set<int> s;
    for(int i=1;i<=N;i++) s.insert(i);

    while(s.size()>1){
        vector<bool>vis(N+1);
        set<int> e;
        function<void(int)> dfs = [&] (int nd){
            vis[nd]=1;
            if(e.size()<(s.size()/2)) e.insert(nd);
            else return;
            for(auto u : t[nd])
                if(!vis[u] && s.find(u)!=s.end())
                    dfs(u);
        };
        dfs(*s.begin());
        if(!query(vector(e.begin(), e.end()))){
            set<int> m;
            for(auto x : s) 
                if(e.find(x)==e.end())
                    m.insert(x);
            s = m;
        }else 
            s=e;
    }
    return *s.begin();
}

Subtask #1
26.4 / 40.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 480 KB Number of queries: 10
2 Partially correct 10 ms 492 KB Number of queries: 24
3 Partially correct 17 ms 508 KB Number of queries: 23
4 Runtime error 1 ms 520 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 532 KB Number of queries: 11
2 Partially correct 16 ms 516 KB Number of queries: 15
3 Partially correct 18 ms 516 KB Number of queries: 22
4 Runtime error 1 ms 516 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -