oj.uz

Submission #1088238

# Submission time Handle Problem Language Result Execution time Memory
1088238 2024-09-14T07:05:47 Z vahagng Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 184 ms 131072 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;

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)
{
    cnt = 0;
    for(int i = 1; i <= N; i++){
        kara[i] = true;
        visited[i] = false;
        total++;
    }
    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 600 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 177 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 184 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -