oj.uz

답안 #269785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
269785 2020-08-17T10:17:45 Z egekabas Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 2 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;
        if(lft <= 0) return;
        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);
    }
    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);
        int cnt = 0;
        for(auto u : sel)
            cnt += (nope[u] == 0);
        assert(cnt == clean/2);
        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;
        }
    }
}
/*int main(){
    cout << findEgg(4, {{1, 2}, {2, 3}, {3, 4}}) << '\n';
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}*/

Subtask #1
0.0 / 40.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 640 KB The found island is incorrect
2 Halted 0 ms 0 KB -