제출 #1141465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141465		SpartanCode	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	140 ms	528 KiB

eastereggs

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

using namespace std;

map<int,vector<int>> adj;

pair<int,int> masLejano(int x, int padre)
{
    pair<int,int> res = {x, 0}, temp;
    for(int i = 0; i < adj[x].size(); i++)
        if(adj[x][i] != padre)
        {
            temp = masLejano(adj[x][i], x);
            temp.second++;
            if(temp.second > res.second)
                res = temp;
        }
    return res;
}

pair<int,pair<int,int>> diametro(int x)
{
    pair<int,int> a, b;
    a = masLejano(x, x);
    b = masLejano(a.first, a.first);
    return {b.second, {b.first, a.first}};
}

void seccion(int x, int padre ,int dist, set<int> &vec)
{
    if(dist < 0)
        return ;
    vec.insert(x);
    for(int i = 0; i < adj[x].size(); i++)
        if(adj[x][i] != padre)
            seccion(adj[x][i], x, dist-1, vec);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    
    while(adj.size() > 0)
        adj.erase(adj.begin());
    
    if(N == 1)
        return 1;
    //cout << "-----------\n";

    for(int i = 0; i < N-1; i++)
    {
        if(!adj.count(bridges[i].first))
            adj.insert({bridges[i].first, vector<int> (0)});
        if(!adj.count(bridges[i].second))
            adj.insert({bridges[i].second, vector<int> (0)});

        adj[bridges[i].first].push_back(bridges[i].second);
        adj[bridges[i].second].push_back(bridges[i].first);
    }

    int ini = bridges[0].first;

    while(true)
    {
        pair<int,pair<int,int>> dmtr = diametro(ini);
        set<int> a, b;
        int mit = dmtr.first/2;

        /*cout << "\n";
        cout << dmtr.first << " -> " << dmtr.second.first << " " << dmtr.second.second << "\n";*/

        seccion(dmtr.second.first, 0, mit, a);
        if(dmtr.first%2 == 1)
            mit++;
        seccion(dmtr.second.second, 0, mit, b);

        //Debo de separar las dos secciones
        //Las dos secciones se unen con una arista, la cual debo cortar
        int mitad;
        for(auto it : a)
            if(b.count(it))
            {
                mitad = it;
                b.erase(mitad);
                break;
            }
        int intruso;
        for(int i = 0; i < adj[mitad].size(); i++)
            if(b.count(adj[mitad][i]))
            {
                intruso = adj[mitad][i];
                adj[mitad].erase(adj[mitad].begin()+i);
                for(int j = 0; j < adj[intruso].size(); j++)
                    if(adj[intruso][j] == mitad)
                    {
                        adj[intruso].erase(adj[intruso].begin()+j);
                        break;
                    }
                break;
            }
        a.clear();
        seccion(mitad, 0, mit, a);
        vector<int> question;
        for(auto it : a)
            question.push_back(it);
        if(query(question))
        {
            ini = *a.begin();
            if(a.size() == 1)
                return *a.begin();
        }
        else
        {
            ini = *b.begin();
            if(b.size() == 1)
                return *b.begin();
        }

        
        /*for(auto it : a)
            cout << it << " ";
        cout << " -> ";
        for(auto it : b)
            cout << it << " ";
        cout << "\n";*/
    }

}

/*int main()
{
    int n, a, b;
    cin >> n;
    vector<pair<int,int>> vec;
    for(int i = 0; i <n-1; i++)
    {
        cin >> a >> b;
        vec.push_back({a, b});
    }
    findEgg(n, vec);

    return 0;
}*/

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