Submission #1164714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164714		adaawf	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1087 ms	2532 KiB

eastereggs

#include <iostream>
#include <vector>
#include "grader.h"
using namespace std;
vector<int> g[555];
int dd[555], f[555][555], da[555], pp[555][555], db[555];
void dfs(int x, int p, int h, int c) {
    c += dd[x];
    f[h][x] = c;
    pp[h][x] = p;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x, h, c);
    }
}
int findEgg(int n, vector<pair<int, int>> e) {
    for (int i = 0; i < n - 1; i++) {
        g[e[i].first].push_back(e[i].second);
        g[e[i].second].push_back(e[i].first);
    }
    for (int i = 1; i <= n; i++) dd[i] = 1;
    int h = n;
    while (h != 1) {
        for (int i = 1; i <= n; i++) {
            dfs(i, -1, i, 0);
            da[i] = 0;
        }
        vector<int> v, vv;
        for (int i = 1; i <= n; i++) {
            if (dd[i] == 1) {
                v.push_back(i);
                vv.push_back(i);
                da[i] = 1;
                break;
            }
        }
        int j = 0;
        while (v.size() < (h + 1) / 2) {
            int k = v[j];
            for (int i = 1; i <= n; i++) {
                if (f[k][i] == 2 && da[i] == 0 && dd[i] == 1) {
                    v.push_back(i);
                    int l = i;
                    while (da[l] == 0) {
                        vv.push_back(l);
                        da[l] = 1;
                        l = pp[k][l];
                    }
                }
                if (v.size() == (h + 1) / 2) break;
            }
            j++;
        }
        for (int i = 1; i <= n; i++) db[i] = 0;
        for (int w : v) db[w] = 1;
        if (query(vv)) {
            for (int i = 1; i <= n; i++) {
                dd[i] = db[i];
            }
            h = v.size();
        }
        else {
            for (int i = 1; i <= n; i++) {
                if (dd[i] == 1 && db[i] == 0) {
                    dd[i] = 1;
                }
                else dd[i] = 0;
            }
            h -= v.size();
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dd[i] == 1) return i;
    }
    return -1;
}

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