Submission #1145926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145926		SimonaIvanova	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	508 KiB

eastereggs

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include "grader.h"
#define endl '\n'
using namespace std;
int query(vector < int > islands);
vector <int> v1[600], v2;
int n;
int used[600];
void dfs(int beg)
{
    v2.push_back(beg);
    used[beg] = 1;
    for(int i = 0; i < v1[beg].size(); i++)
    {
        if(!used[v1[beg][i]])
            dfs(v1[beg][i]);
    }
}
void fill_v1(int N, vector <pair <int, int> > bridges)
{
    n = N;
    for(int i = 1; i <= n; i++)
    {
        v1[i].clear();
    }
    for(int i = 0; i < bridges.size(); i++)
    {
        v1[bridges[i].first].push_back(bridges[i].second);
        v1[bridges[i].second].push_back(bridges[i].first);
    }
}
bool check(int mid)
{
    vector <int> q;
    for(int i = 0; i <= mid; i++)
        q.push_back(v2[i]);
    return query(q);
}
int bin_search()
{
    int l = 0, r = v2.size()-1;
    while(l < r)
    {
        int mid = (l+r)/2;
        ///cout << mid << " " << l << " " << r << endl;
        if(check(mid) == 1)
            r = mid;
        else
            l = mid+1;
    }
    return v2[l];
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
    fill_v1(N, bridges);
    memset(used, 0, sizeof(used));
    v2.clear();
    dfs(1);
    /*for(int i = 0; i < v2.size(); i++)
    {
        cout << v2[i] << " ";
    }
    cout << endl;*/
    return bin_search();
}

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