Submission #1146454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146454		aliarapov	Easter Eggs (info1cup17_eastereggs)	C++20	71.60 / 100	11 ms	464 KiB

eastereggs

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

using namespace std;

const int n = 513;
vector<int> g[n];
vector<int> sz(n);
vector<int> par(n);
vector<bool> bad(n);

void dfs(int v) {
    for (int to : g[v]) {
        if (to != par[v]) par[to] = v, dfs(to);
    }
}

void getsz(int v) {
    sz[v] = 1;
    for (int to : g[v]) {
        if (to != par[v] and !bad[to]) getsz(to), sz[v] += sz[to];
    }
}

int get(int v, int root) {
    for (int to : g[v]) {
        if (to != par[v] and sz[to] * 2 >= sz[root] and !bad[to]) return get(to, root);
    }
    return v;
}

vector<int> getdown(int v) {
    vector<int> ans = {v};
    for (int to : g[v]) {
        if (to != par[v] and !bad[to]) {
            auto next = getdown(to);
            for (int i : next) ans.push_back(i);
        }
    }
    return ans;
}

int calc(int v) {
    getsz(v);
    int cen = get(v, v);
    bad[v] = 1;
    bad[cen] = 1;
    if (cen == v) {
        bool ok = 1;
        for (int to : g[v]) {
            if (to != par[v] and !bad[to]) ok = 0;
        }
        if (ok) return v;
        vector<pair<int,int> > to;
        int cnt = 0;
        for (int u : g[v]) {
            if (u == par[v] or bad[u]) continue;
            to.push_back({sz[u], u});
            cnt++;
        }
        sort(to.begin(), to.end());
        for (int i = 0; i < cnt / 2; i++) {
            if (i & 1)
                bad[to[i].second] = 1;
            else bad[to[cnt - i - 1].second] = 1;
        }
        if (query(getdown(v))) {
            return calc(v);
        } else {
            for (auto [val, u] : to) bad[u] = !bad[u];
            return calc(v);
        }
    }
    bool down = query(getdown(cen));

    if (!down) {
        return calc(v);
    } else if (down) {
        return calc(cen);
    } 
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (auto [u, v] : bridges) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    int ans = calc(1);
    for (int i = 1; i <= N; i++) {
        bad[i] = 0;
        g[i].clear();
    }
    return ans;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int calc(int)':
eastereggs.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

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