oj.uz

Submission #1088247

# Submission time Handle Problem Language Result Execution time Memory
1088247 2024-09-14T07:14:25 Z vahagng Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 10 ms 600 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 344 KB Number of queries: 4
3 Correct 0 ms 344 KB Number of queries: 4
4 Correct 1 ms 344 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Number of queries: 8
2 Correct 6 ms 344 KB Number of queries: 9
3 Correct 10 ms 344 KB Number of queries: 9
4 Correct 9 ms 600 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Number of queries: 9
2 Correct 8 ms 488 KB Number of queries: 9
3 Correct 10 ms 492 KB Number of queries: 9
4 Correct 9 ms 596 KB Number of queries: 9