oj.uz

Submission #569567

# Submission time Handle Problem Language Result Execution time Memory
569567 2022-05-27T14:02:19 Z d4xn Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 14 ms 476 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

//const int N = 512;
const int N = 520;

int n;
vector<vector<int>> adj;
vector<bool> vis;
vector<bool> r;
vector<int> p;
vector<int> sz;
vector<int> q;

void dfs1(int u = 0, int par = -1) {
  p[u] = par;

  for (int &v : adj[u]) {
    if (v == par) continue;
    dfs1(v, u);
  }
}

void dfs2(int u) {
  vis[u] = 1;
  sz[u] = 1;

  for (int &v : adj[u]) {
    if (v == p[u] || r[v]) continue;
    dfs2(v);
    sz[u] += sz[v];
  }
}

int findSubtree(int ssz) {
  for (int i = 0; i < n; i++) {
    if (!r[i] && sz[i] == ssz) return i;
  }
  return -1; // never reached
}

void fillQuery(int u) {
  q.push_back(u+1);

  for (int &v : adj[u]) {
    if (v == p[u] || r[v]) continue;
    fillQuery(v);
  }
}

int findEgg (int N, vector < pair < int, int > > bridges) 
{
  n = N;

  adj.clear();
  adj.resize(N);
  vis.clear();
  vis.resize(N, 0);
  r.clear();
  r.resize(N, 0);
  p.clear();
  p.resize(N, -1);
  sz.clear();
  sz.resize(N, 1);
  q.clear();

  for (auto &[x, y] : bridges) {
    adj[x-1].push_back(y-1);
    adj[y-1].push_back(x-1);
  }

  dfs1();

  int x = n;
  while (x != 1) {
    vis.clear();
    vis.resize(N, 0);
    for (int i = 0; i < n; i++) {
      if (vis[i] || r[i] || (p[i] != -1 && !r[p[i]])) continue;
      dfs2(i);
    }

    int mid = x/2;
    int u = findSubtree(mid);
    if (u == -1) {
      mid++;
      u = findSubtree(mid);
    }
    if (u == -1) {
      mid++;
      u = findSubtree(mid);
    }
    if (u == -1) {
      mid -= 3;
      u = findSubtree(mid);
    }
    assert(u != -1);

    q.clear();
    fillQuery(u);
    if (query(q)) {
      for (int i = 0; i < n; i++) {
        r[i] = 1;
      }
      for (int &i : q) r[i-1] = 0;
      x = mid;
    }
    else {
      for (int &i : q) r[i-1] = 1;
      x -= mid;
    }
  }

  vis.clear();
  vis.resize(N, 0);
  for (int i = 0; i < n; i++) {
    if (vis[i] || r[i] || (p[i] != -1 && !r[p[i]])) continue;
    dfs2(i);
  }

  int ans = findSubtree(1);
  assert(ans != -1);
  return ans + 1;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Runtime error 1 ms 336 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Number of queries: 8
2 Runtime error 1 ms 476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 336 KB Number of queries: 9
2 Runtime error 1 ms 464 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -