Submission #1141391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141391		Maaxle	Easter Eggs (info1cup17_eastereggs)	C++20	71.60 / 100	6 ms	492 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

#define range(it, a, b) for (ll it = a; it < b; it++)
#define invr(it, a, b) for (ll it = a; it >= b; it--)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define ld long double
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>
#define v(x) vector<x>

using namespace std;

int n;
v(v(int)) adj;
v(int) stree;
v(bool) blocked;

void get_subtree(int i, int p) {
    stree[i] = 1; 

    for (int k : adj[i]) {
        if (k == p || blocked[k])
            continue;
        get_subtree(k, i);
        stree[i] += stree[k];
    }
}

ll get_centroid(int i, int p, int& m) {
    for (ll k : adj[i]) {
        if (k == p || blocked[k])
            continue;
        if (stree[k] > m/2)
            return get_centroid(k, i, m);
    }
    return i;
}

void fill_set (v(int)& st, int i, int p) {
    st.push_back(i+1);
    for (int k : adj[i]) {
        if (k == p || blocked[k])
            continue;
        fill_set(st, k, i);
    }
}

int find(int rt) {
    // printf("---STEP [%d]---\n", rt);
    get_subtree(rt, -1);
    int m = stree[rt];

    if (m == 1)
        return rt;
    if (m == 2) {
        if (query({rt+1}))
            return rt;
        for (int it : adj[rt]) {
            if (!blocked[it])
                return it;
        }
    }

    int c = get_centroid(rt, -1, m);
    // printf("[Centroid]: %d\n", c+1);

    get_subtree(c, -1);

    vector<pair<int, int>> cent_adj;
    for (ll k : adj[c]) {
        if (blocked[k])
            continue;
        cent_adj.push_back({stree[k], k});
    }
    sort(all(cent_adj));

    v(int) q = {c+1}, used, nused;
    ll aux = m/2;
    for (auto& it : cent_adj) {
        if (it.first <= aux) {
            aux -= it.first;
            used.push_back(it.second);
            fill_set(q, it.second, c);
        }
        else nused.push_back(it.second);
    }

    // printf("[Set]: ");
    // for (int it : q) 
    //     printf("%d ", it);
    // printf("\n");

    int ans = query(q);
    // printf("[Query]: %d\n", ans);
    // printf("[Deleted]: ");
    if (ans) {
        for (int& it : nused) {
            blocked[it] = 1;
            // printf("%d ", it+1);
        }
    }
    else {
        for (int& it : used) {
            blocked[it] = 1;
            // printf("%d ", it+1);
        }
    }
    // printf("\n");

    return find(c);
}

int findEgg (int N, vector < pair < int, int > > bridges) {
    adj.clear();
    adj.resize(N);

    stree.resize(N);

    blocked.clear();
    blocked.resize(N);
    n = N;
    
    for (auto& it : bridges) {
        adj[it.first-1].push_back(it.second-1);
        adj[it.second-1].push_back(it.first-1);
    }

    return find(0)+1;
}

• Subtask 1: 32 / 40
• Subtask 2: 26.4 / 40
• Subtask 3: 13.2 / 20