oj.uz

Submission #802471

# Submission time Handle Problem Language Result Execution time Memory
802471 2023-08-02T12:25:05 Z raysh07 Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 2 ms 1872 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int n;
const int maxn = 513;
vector <int> adj[maxn];
int sz[maxn];
bool there[maxn];
vector <int> sub[maxn];

void dfs(int u, int par = -1){
    sz[u] = 1;
    sub[u].clear();
    sub[u].push_back(u);
    
    for (int v : adj[u]){
        if (v != par && there[v]){
            dfs(v, u);
            sz[u] += sz[v];
            for (auto x : sub[v]) sub[u].push_back(x);
        }
    }
}

int findEgg (int N, vector <pair<int,int>> bridges)
{
    n = N;
    for (int i = 1; i <= n; i++) adj[i].clear();
    
    for (auto [u, v] : bridges){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector <int> poss;
    for (int i = 1; i <= n; i++) {
        poss.push_back(i);
        there[i] = true;
    }
    
    while (poss.size() != 1){
        n = poss.size();
        bool found = false;
        
        for (auto x : poss){
            if (found) break;
            dfs(x);
            for (auto y : poss){
                if (sz[y] == n / 2){
                    found = true;
                    
                    vector <int> v1;
                    for (auto z : sub[y]) v1.push_back(z);
                    
                    if (query(v1)){
                        poss = v1;
                    } else {
                        set <int> v2;
                        for (auto z : poss) v2.insert(z);
                        for (auto z : sub[y]) v2.erase(z);
                        poss.clear();
                        for (auto z : v2) poss.push_back(z);
                    }
                    break;
                }
            }
        }
        
        for (int i = 1; i <= n; i++) there[i] = false;
        for (auto z : poss) there[z] = true;
        
        assert(found);
    }
    
    return poss[0];
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 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 848 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 2 ms 1872 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -