Submission #1141396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141396		hyl_kibou	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	22 ms	552 KiB

eastereggs

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

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges)
{
    //if (query ({1})) return 1;
    int a, b;
    std::set<int> con[N+3];
    std::set<int> set;
    int arr[N+3] = {};

    for(auto x : bridges){
        a = x.first;
        b = x.second;

        set.insert(a);
        set.insert(b);

        con[a].insert(b);
        con[b].insert(a);
    }

    std::vector<int> test;
    std::vector<int> cat;

    int round = 1;
    int senders = 0;
    int total = (N+1)/2;
    int ans;
    a = 1;
    while(true){
        test.clear();
        cat.clear();
        std::queue<int> que;
        senders = 0;

        total = (set.size()+1)/2;

        int a = bridges[0].first;

        que.push(a);
        arr[a] = round;
        test.push_back(a);
        if(set.find(a)!=set.end()){
            cat.push_back(a);
            ++senders;
        }

        while(!que.empty()){
            a = que.front();
            que.pop();

            if(senders==total){
                break;
            }
            //printf("%d*\n", a);
            for(int x : con[a]){
                if(arr[x]!=round){
                    que.push(x);
                    arr[x] = round;
                    test.push_back(x);
                    if(set.find(x)!=set.end()){
                        cat.push_back(x);
                        ++senders;
                        if(senders==total){
                            break;
                        }
                    }
                }
            }

        }
        ans = query(test);
        if(ans){
            set.clear();
            for(int x: cat){
                set.insert(x);
            }

        }
        else{
            for(int x: test){
                set.erase(x);
            }
        }

        /*
        for(int x : set){
            printf("%d ", x);
        }
        printf("\n");
        //*/

        if(set.size()==1){
            return *set.begin();
        }

        ++round;
    }

    return 0;
}

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