Submission #1145765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145765		SimonaIvanova	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	500 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];
int n;
void fill_v1(int N, vector < pair < int, int > > bridges)
{
    n = N;
    int m = bridges.size();
    for(int i = 0; i < m; i++)
    {
        v1[bridges[i].first].push_back(bridges[i].second);
        v1[bridges[i].second].push_back(bridges[i].first);
    }
}
vector <int> q;
int used[600];
void dfs(int beg)
{
    used[beg] = 1;
    q.push_back(beg);
    int sz = v1[beg].size();
    for(int i = 0; i < sz; i++)
    {
        if(!used[v1[beg][i]])
        {
            dfs(v1[beg][i]);
        }
    }
}
int ans;
void dnc(int beg)
{
    int sz = v1[beg].size();
    for(int i = 0; i < sz; i++)
    {
        q.clear();
        dfs(v1[beg][i]);
        if(i == 0)
        {
            q.push_back(beg);
        }
        if(query(q) == 1)
        {
            if(q.size() == 1)
            {
                ans = q[0];
                return;
            }
            dnc(v1[beg][i]);
            return;
        }
    }
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
    fill_v1(N, bridges);
    dnc(1);
    return ans;
}

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