oj.uz

Submission #269797

# Submission time Handle Problem Language Result Execution time Memory
269797 2020-08-17T10:26:28 Z egekabas Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 30 ms 400 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
/*int query(vector < int > islands){
    cout << "-> ";
    for(auto u : islands)
        cout << u << ' ';
    cout << '\n';
    int ret;
    cin >> ret;
    return ret;
}*/
vector<int> g[600];
int nope[600];
int block[600];
vector<int> sel;
int lft;
void dfs(int v, int prt){
    if(block[v]) return;
    if(lft <= 0) return;
    sel.pb(v);
    if(nope[v] == 0)
        --lft;
    for(auto u : g[v]){
        if(u == prt) continue;
        dfs(u, v);
    }
}
int findEgg(int N, vector<pair<int, int>> bridges){
    sel.clear();
    for(int i = 1; i <= N; ++i){
        nope[i] = block[i] = 0;
        g[i].clear();
    }
    for(auto u : bridges){
        g[u.ff].pb(u.ss);
        g[u.ss].pb(u.ff);
    }
    while(1){
        int clean = 0;
        for(int i = 1; i <= N; ++i)
            if(nope[i] == 0 && block[i] == 0)
                ++clean;
        if(clean == 1){
            for(int i = 1; i <= N; ++i)
                if(nope[i] == 0 && block[i] == 0)
                    return i;
        }
        lft = clean/2;
        sel.clear();
        for(int i = 1; i <= N; ++i)
            if(block[i] == 0){
                dfs(i, 0);
                break;
            }
        if(query(sel)){
            for(int i = 1; i <= N; ++i)
                block[i] = 1;
            for(auto u : sel)
                block[u] = 0;    
        }
        else{
            for(auto u : sel)
                nope[u] = 1;
        }
    }
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 400 KB Number of queries: 8
2 Correct 15 ms 384 KB Number of queries: 9
3 Correct 30 ms 384 KB Number of queries: 9
4 Correct 21 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 384 KB Number of queries: 9
2 Correct 23 ms 384 KB Number of queries: 9
3 Correct 28 ms 384 KB Number of queries: 9
4 Correct 21 ms 384 KB Number of queries: 9