oj.uz

Submission #1088241

# Submission time Handle Problem Language Result Execution time Memory
1088241 2024-09-14T07:09:55 Z vahagng Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 4 ms 604 KB 
#include <bits/stdc++.h>
#include "grader.h"
 
using namespace std;

vector<int>comp;
vector<int>adj[514];
bool visited[514];
bool kara[514];
int total, 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];
    if(cnt == total/2) return;
    for(auto i : adj[node]){
        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
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -