Submission #1070981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070981		raduv	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	16 ms	740 KiB

eastereggs

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

using namespace std;

const int MAXN = 512;
vector<int> adj[MAXN + 1];
vector<int> islands;
bitset <MAXN + 1> frecv;
void dfs(int node){
  frecv[node] = 1;
  islands.push_back(node);
  for(auto n : adj[node] ){
    if(frecv[n] == 0)
      dfs(n);
  }
}
int findEgg(int n, vector<pair<int, int>> bridges){
  int i, st, dr, mij, u, v;
  frecv.reset();
  for( i = 0; i <= MAXN; i++ )
    adj[i].clear();
  islands.clear();
  for( auto pi : bridges ){
    u = pi.first;
    v = pi.second;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1);
  st = 0;
  dr = n;
  while(dr - st > 1){
    //cout << islands[0] << " ";
    mij = (dr + st) / 2;
    vector <int> qry;
    qry.clear();
    for( i = 0; i < mij; i++ ){
      qry.push_back(islands[i]);
    }
    if(query(qry))
      dr = mij;
    else
      st = mij;
  }
  return islands[st];
}

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