답안 #964860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964860 2024-04-17T16:44:08 Z TAhmed33 통행료 (IOI18_highway) C++17
18 / 100
107 ms 16524 KB
#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
  return uniform_int_distribution <int> (l, r) (rng);
}
vector <pair <int, int>> adj[MAXN];
vector <int> ett, ett2;
int in[MAXN], out[MAXN], dep[MAXN], tt;
void dfs (int pos, int par) {
  in[pos] = ++tt; 
  for (auto j : adj[pos]) {
    if (j.first == par) continue;
    ett.push_back(j.second);
    dep[j.first] = 1 + dep[pos];
    dfs(j.first, pos);
  }
  out[pos] = tt;
}
void dfs2 (int pos) {
  for (auto j : adj[pos]) {
    if (in[j.first] < in[pos]) continue;
    ett2.push_back(j.second);
    dfs2(j.first);
  }
}
void find_pair (int n, vector <int> u, vector <int> v, int a, int b) {
  for (int i = 0; i + 1 < n; i++) {
    adj[u[i]].push_back({v[i], i});
    adj[v[i]].push_back({u[i], i});
  }
  vector <int> g(n - 1);
  ll U = ask(g);
  dfs(0, -1);
  for (int i = 0; i < n - 1; i++) {
    if (dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
  }
  int l = 0, r = n - 2, p1 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (int j = 0; j <= mid; j++) g[ett[j]] = 1;
    ll V = ask(g);
    if (V != U) {
      r = mid - 1; p1 = mid;
    } else {
      l = mid + 1;
    }
  }
  l = 0, r = n - 2; int p2 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (int j = mid; j + 1 < n; j++) g[ett[j]] = 1;
    ll V = ask(g);
    if (V != U) {
      l = mid + 1; p2 = mid;
    } else {
      r = mid - 1;
    }
  }
  p1 = ett[p1]; p2 = ett[p2];
  if (in[u[p1]] <= in[v[p2]] && out[v[p2]] <= out[u[p1]]) {
    answer(u[p1], v[p2]);
    return;
  }
  dfs2(v[p1]);
  l = 0, r = (int)ett2.size() - 1; int ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (int i = mid; i < (int)ett2.size() - 1; i++) {
      g[ett2[i]] = 1;
    }
    ll V = ask(g);
    if (V != U) {
      l = mid + 1; ans = mid;
    } else {
      r = mid - 1;
    }
  }
  answer(v[ans], v[p2]);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3800 KB Output is correct
2 Correct 1 ms 3800 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 1 ms 3796 KB Output is correct
6 Correct 2 ms 3796 KB Output is correct
7 Correct 2 ms 3804 KB Output is correct
8 Correct 1 ms 3800 KB Output is correct
9 Correct 1 ms 3800 KB Output is correct
10 Correct 2 ms 3800 KB Output is correct
11 Correct 1 ms 3800 KB Output is correct
12 Correct 1 ms 3800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3852 KB Output is correct
2 Correct 13 ms 4576 KB Output is correct
3 Correct 83 ms 9680 KB Output is correct
4 Correct 82 ms 9796 KB Output is correct
5 Correct 95 ms 9588 KB Output is correct
6 Correct 79 ms 9808 KB Output is correct
7 Correct 93 ms 9812 KB Output is correct
8 Correct 90 ms 9824 KB Output is correct
9 Correct 92 ms 10280 KB Output is correct
10 Correct 83 ms 9572 KB Output is correct
11 Correct 92 ms 11156 KB Output is correct
12 Correct 84 ms 11692 KB Output is correct
13 Correct 90 ms 11128 KB Output is correct
14 Correct 79 ms 10300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5288 KB Output is correct
2 Correct 17 ms 6912 KB Output is correct
3 Correct 25 ms 8048 KB Output is correct
4 Correct 68 ms 16060 KB Output is correct
5 Correct 75 ms 16524 KB Output is correct
6 Correct 81 ms 16308 KB Output is correct
7 Correct 107 ms 16268 KB Output is correct
8 Correct 77 ms 16060 KB Output is correct
9 Correct 94 ms 16056 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3856 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4124 KB Incorrect
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4184 KB Incorrect
2 Halted 0 ms 0 KB -