Submission #1141523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141523		ArtieAaron	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	7 ms	536 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
typedef long long lli;
typedef vector<lli> vi;
typedef pair<lli, lli> ii;
typedef vector<ii> vii;
#define f first
#define s second
#define pb push_back
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define SL '\n'
#define fore(a,b,c) for(lli a = (b), fgh = (c); a < fgh; a ++)
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void dfs(int pos, int par, vector<set<int>> &adj, vector<int> &tam){
    tam[pos] = 1;
    for(auto &i: adj[pos]){
        if(i == par) continue;
        dfs(i, pos, adj, tam);
        tam[pos] += tam[i];
    }
}

void subar(int pos, int par, vector<set<int>> &adj, vector<int> &q){
    q.pb(pos+1);
    for(auto &i: adj[pos]){
        if(i == par) continue;
        subar(i, pos, adj, q);
    }
}

int findEgg(int N, vector<pair<int, int>> bridges){
    int root = 0;
    vector<set<int>> adj(N);
    for(auto &i: bridges){
        i.f --, i.s --;
        adj[i.f].insert(i.s);
        adj[i.s].insert(i.f);
    }
    vector<int> tam(N);
    dfs(root, root, adj, tam);
    while(tam[root] != 1){
        int cent = root, par = root, sub, mx;
        while(true){
            sub = -1, mx = 0;
            for(auto &i: adj[cent]){
                if(i == par) continue;
                if(tam[i] > mx){
                    mx = tam[i], sub = i;
                }
            }
            if(sub == -1 or mx <= tam[root]/2) break;
            par = cent, cent = sub;
        }
        vector<int> q;
        subar(sub, cent, adj, q);
        if(query(q)){
            auto o = adj[sub].lower_bound(cent);
            adj[sub].erase(o);
            root = sub;
        } else {
            auto o = adj[cent].lower_bound(sub);
            adj[cent].erase(o);
        }
        dfs(root, root, adj, tam);
    }
    return root+1;
}

• Subtask 1: 10 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20