oj.uz

Submission #269778

# Submission time Handle Problem Language Result Execution time Memory
269778 2020-08-17T10:14:12 Z egekabas Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 4 ms 640 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){
    for(auto u : bridges){
        g[u.ff].pb(u.ss);
        g[u.ss].pb(u.ff);
    }
    for(int times = 0; times < 10; ++times){
        int clean = 0;
        for(int i = 1; i <= N; ++i)
            if(nope[i] == 0 && block[i] == 0)
                ++clean;
        lft = clean/2;
        sel.clear();
        for(int i = 1; i <= N; ++i)
            if(block[i] == 0)
                dfs(i, 0);
        if(sel.size() && 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;
        }
    }
    for(int i = 1; i <= N; ++i)
        if(nope[i] == 0 && block[i] == 0)
            return i;
}
/*int main(){
    cout << findEgg(3, {{1, 2}, {1, 3}}) << '\n';
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}*/

Compilation message

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

Subtask #1
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB The found island is incorrect
2 Halted 0 ms 0 KB -