Submission #1141393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141393		josephtenorio	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	11 ms	484 KiB

eastereggs

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


using namespace std;

void atac(int sum, vector<bool> &pos, vector<vector<int>> &adj) {
    //cout << "sum: " << sum << endl;
    //for (auto ab: pos) {
    //    cout << ab << " ";
    //}
    //cout << endl;

    int ya = 0;
    vector<int> isla;
    vector<bool> visi(pos.size(), 0);
    queue<int> bfs;
    visi[0] = 1;
    isla.push_back(1);
    for (auto to: adj[0]) {
        bfs.push(to);
        //cout << to << ".push ";
    }
    //cout << endl;
    ya += pos[0];
    while (ya != sum) {
        int act = bfs.front();
        bfs.pop();
        visi[act] = 1;
        ya += pos[act];
        isla.push_back(act + 1);
        for (auto to: adj[act]) {
            if (!visi[to]) {
                bfs.push(to);
            }
        }
    }
    if (query(isla)) {
        vector<bool> sal(pos.size(), 0);
        for (auto to: isla) {
            to --;
            sal[to] = 1;
        }
        for (int t1 = 0; t1 < pos.size(); t1 ++) {
            if (!sal[t1]) {
                pos[t1] = 0;
            }
        }
    } else {
        for (auto to: isla) {
            to --;
            pos[to] = 0;
        }
    }
    return ;
}

int sump(vector<bool> pos) {
    int sum = 0;
    for (bool po: pos) {
        sum += po;
    }
    return sum;
}

int findEgg (int n, vector<pair<int, int>> in) {
    int a, b;
    vector<vector<int>> adj(n);
    vector<bool> pos(n, 1);
    for (int t1 = 0; t1 < n-1; t1++) {
        a = in[t1].first - 1;
        b = in[t1].second - 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    while (sump(pos) != 1) {
        atac(sump(pos) / 2, pos, adj);
    }
    int re = 0;
    for (int t1 = 0; t1 < n; t1 ++) {
        //cout << pos[t1] << " ";
        if (pos[t1]) {
            re = t1 + 1;
        }
    }
    //cout << endl;
    return re;
}

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