제출 #802471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802471		raysh07	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	2 ms	1872 KiB

eastereggs

#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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20