oj.uz

Submission #1070981

# Submission time Handle Problem Language Result Execution time Memory
1070981 2024-08-22T22:16:27 Z raduv Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 16 ms 740 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 340 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 1 ms 344 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Number of queries: 8
2 Correct 10 ms 484 KB Number of queries: 9
3 Correct 13 ms 496 KB Number of queries: 9
4 Correct 13 ms 740 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 520 KB Number of queries: 9
2 Correct 8 ms 500 KB Number of queries: 9
3 Correct 11 ms 600 KB Number of queries: 9
4 Correct 15 ms 492 KB Number of queries: 9