Submission #756718

#	Time	Username	Problem	Language	Result	Execution time	Memory
756718		andrei_marciuc	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	1 ms	592 KiB

eastereggs

#include <iostream>
#include <vector>
#include <bitset>
#include "grader.h"

using namespace std;

const int MAX = 514;

vector<int> adj[ MAX ];
vector<int> island;
vector<int> parc;
bitset<MAX + 2> ok;

void dfs( int nod = 1 ) {
    ok[ nod ] = 1;
    parc.push_back( nod );
    for( const int nxt : adj[ nod ] )
        if( !ok[ nxt ] )
            dfs( nxt );
}

int findEgg( int n, vector<pair<int, int>> bridges ) {
    for( const auto muchie : bridges ) {
        adj[ muchie.first ].push_back( muchie.second );
        adj[ muchie.second ].push_back( muchie.first );
    }

    dfs();

    int left = 0;
    int right = parc.size() - 1;
    while( left < right ) {
        int med = ( left + right ) / 2;
        
        island.clear();
        for( int i = left; i <= med; i++ )
            island.push_back( parc[ i ] );

        if( query( island ) )
            right = med;
        else left = med + 1;
    }
    return right;
}

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