oj.uz

Submission #649501

# Submission time Handle Problem Language Result Execution time Memory
649501 2022-10-10T10:07:34 Z yelul Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 20 ms 468 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> o;
vector<vector<int>> g(520);

void order(int x, int t) {
  o.push_back(x);
  for (int i : g[x]) {
    if (i == t)
      continue;
    order(i, x);
  }
}

int findEgg(int N, vector < pair < int, int > > bridges) {
  
  for (auto p : bridges) {
    int u = p.first, v = p.second;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  
  order(1, -1);

  int l = 0, r = N-2, mid, x = N-1;
  while (l <= r) {
    mid = (l+r)/2;
    vector<int> a;
    for (int i=0; i<=mid; i++)
      a.push_back(o[i]);
    if (query(a)) {
      r = mid-1;
      x = mid;
    } else {
      l = mid+1;
    }
  }

  int ans = o[x];
  o.clear();
  for (int i=0;i<=N;i++) 
    g[i].clear();
  
  return ans;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Number of queries: 8
2 Correct 15 ms 340 KB Number of queries: 9
3 Correct 20 ms 352 KB Number of queries: 9
4 Correct 13 ms 468 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 364 KB Number of queries: 9
2 Correct 16 ms 336 KB Number of queries: 9
3 Correct 17 ms 336 KB Number of queries: 9
4 Correct 20 ms 348 KB Number of queries: 9