oj.uz

답안 #282490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282490 2020-08-24T13:07:56 Z Haunted_Cpp 통행료 (IOI18_highway) C++17
51 / 100
 177 ms 30072 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int MAX_N = 9e4 + 5;

vector<vector<pair<int, int>>> g(MAX_N);

vector<int> up(MAX_N);
vector<pair<int, int>> dist;
vector<vector<pair<int, int>>> h(MAX_N);

int Time = 0;
vector<int> in(MAX_N), out(MAX_N);

int _A, _B, max_h = 0;

void calc(int node, int p, int height, int where) {
  in[node] = ++Time;
  max_h = max(max_h, height);
  up[node] = where;
  h[height].emplace_back(up[node], node);
  for (auto to : g[node]) {
    if (to.first != p) {
      calc(to.first, node, height + 1, to.second);
    }
  }
  out[node] = Time;
}

int st;

bool in_sub(int u, int v) {
  return in[u] <= in[v] && out[u] >= out[v];
}

void dfs(int node, int p, i64 goal_distance, i64 w) {
  if (w == goal_distance) {
    if (in_sub(node, st) == false) {
      dist.emplace_back(up[node], node);
    } else {
      for (auto to : g[node]) {
        if (in[to.first] < in[node]) continue;
        if (in_sub(to.first, st) == true) {
          dist.emplace_back(to.second, node);
          break;
        }
      }
    }
  }
  for (auto to : g[node]) {
    if (to.first != p) {
      dfs(to.first, node, goal_distance, w + _A);
    }
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  _A = A;
  _B = B;
  const int m = (int) U.size();
  for (int i = 0; i < m; i++) {
    const int u = U[i];
    const int v = V[i];
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }
  calc(0, -1, 0, -1);
  vector<int> q(m);
  const i64 shortest_path = ask(q);
  int lo = 1, hi = max_h + 1;
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = max_h; i >= mid; i--) {
      for (auto to : h[i]) {
        q[to.first] = 1;
      }
    }
    i64 new_shortest = ask(q);
    if (new_shortest == shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  --hi;
  const int lowest = hi;
  assert(hi > 0);
  lo = 0;
  hi = h[hi].size();
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = 0; i <= mid; i++) {
      q[h[lowest][i].first] = 1;
    }
    i64 new_shortest = ask(q);
    if (new_shortest > shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  st = h[lowest][hi].second; 
  dfs(st, -1, shortest_path, 0);
  lo = 0;
  hi = (int) dist.size();
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = 0; i <= mid; i++) {
      const int edge = dist[i].first;
      q[edge] = 1;
    }
    i64 new_shortest = ask(q);
    if (new_shortest > shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  answer(st, dist[hi].second);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 4 ms 5632 KB Output is correct
4 Correct 4 ms 5632 KB Output is correct
5 Correct 4 ms 5632 KB Output is correct
6 Correct 4 ms 5632 KB Output is correct
7 Correct 5 ms 5632 KB Output is correct
8 Correct 5 ms 5664 KB Output is correct
9 Correct 4 ms 5632 KB Output is correct
10 Correct 4 ms 5632 KB Output is correct
11 Correct 4 ms 5632 KB Output is correct
12 Correct 4 ms 5632 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5632 KB Output is correct
2 Correct 16 ms 6272 KB Output is correct
3 Correct 163 ms 11984 KB Output is correct
4 Correct 150 ms 12072 KB Output is correct
5 Correct 149 ms 11936 KB Output is correct
6 Correct 147 ms 11776 KB Output is correct
7 Correct 151 ms 11996 KB Output is correct
8 Correct 145 ms 11864 KB Output is correct
9 Correct 155 ms 12024 KB Output is correct
10 Correct 148 ms 11908 KB Output is correct
11 Correct 162 ms 12868 KB Output is correct
12 Correct 170 ms 14396 KB Output is correct
13 Correct 168 ms 13452 KB Output is correct
14 Correct 161 ms 13428 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 7040 KB Output is correct
2 Correct 30 ms 8560 KB Output is correct
3 Correct 46 ms 10104 KB Output is correct
4 Correct 131 ms 18704 KB Output is correct
5 Correct 125 ms 18780 KB Output is correct
6 Correct 125 ms 18872 KB Output is correct
7 Correct 122 ms 19680 KB Output is correct
8 Correct 116 ms 18696 KB Output is correct
9 Correct 136 ms 18708 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5760 KB Output is correct
2 Correct 18 ms 6376 KB Output is correct
3 Correct 109 ms 10424 KB Output is correct
4 Correct 156 ms 11724 KB Output is correct
5 Correct 146 ms 11860 KB Output is correct
6 Correct 149 ms 11844 KB Output is correct
7 Correct 148 ms 11848 KB Output is correct
8 Correct 145 ms 11920 KB Output is correct
9 Correct 157 ms 11880 KB Output is correct
10 Correct 152 ms 11940 KB Output is correct
11 Correct 153 ms 12964 KB Output is correct
12 Correct 155 ms 13764 KB Output is correct
13 Correct 160 ms 13708 KB Output is correct
14 Correct 161 ms 14032 KB Output is correct
15 Correct 147 ms 11920 KB Output is correct
16 Correct 148 ms 11984 KB Output is correct
17 Correct 165 ms 13388 KB Output is correct
18 Correct 172 ms 14008 KB Output is correct
19 Correct 159 ms 11804 KB Output is correct
20 Correct 177 ms 14472 KB Output is correct
21 Correct 126 ms 13144 KB Output is correct
22 Correct 138 ms 13144 KB Output is correct
23 Correct 147 ms 12576 KB Output is correct
24 Correct 153 ms 13388 KB Output is correct
25 Correct 175 ms 19196 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 30072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 30072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -