Submission #1088247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088247		vahagng	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	10 ms	600 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
 
using namespace std;

vector<int>comp;
vector<int>adj[520];
bool visited[520];
bool kara[520];
int total = 512, cnt, n;

void init(int N){
    n = N;
    for(int i = 1; i <= n; i++){
        adj[i].clear();
    }
    total = 0;
    for(int i = 1; i <= n; i++){
        total++;
        visited[i] = false;
        kara[i] = true;
    }

}

void dfs(int node, int parent){
    visited[node] = true;
    comp.push_back(node);
    cnt += kara[node];
    for(auto i : adj[node]){
        if(cnt == total/2) return;
        if(i == parent) continue;
        dfs(i, node);
    }
}


 
int findEgg (int N, vector<pair<int,int>> bridges)
{
    init(N);
    for(auto i : bridges){
        int u = i.first, v = i.second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    while(total > 1){
        dfs(1,1);
        int pat = query(comp);
        if(pat){
            for(int i = 1; i <= n; i++){
                kara[i] &= visited[i];
            }
        }else{
            for(auto i : comp) kara[i] = false;
        }
        comp.clear();
        cnt = 0;
        total = 0;
        for(int i = 1; i <= n; i++){
            total += kara[i];
            visited[i] = false;
        }
    }
    for(int i = 1; i <= n; i++){
        if(kara[i]) return i;
    }
    return N;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20