oj.uz

Submission #1111973

# Submission time Handle Problem Language Result Execution time Memory
1111973 2024-11-13T13:07:08 Z SalihSahin Highway Tolls (IOI18_highway) C++14
51 / 100
 121 ms 17752 KB 
#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "highway.h"

vector<vector<pair<int, int> > > adj;
vector<vector<int> > depth;
vector<int> d, topar, p;
int mxdep;

void dfs(int node, int par){
  if(node != par) d[node] = d[par] + 1;
  p[node] = par;
  mxdep = max(mxdep, d[node]);
  depth[d[node]].pb(node);

  for(auto itr: adj[node]){
    if(itr.first == par) continue;
    topar[itr.first] = itr.second;
    dfs(itr.first, node);
  }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  adj.resize(N);
  d.resize(N);
  depth.resize(N);
  topar.resize(N);
  p.resize(N);
  mxdep = 0;

  for(int i = 0; i < M; i++){
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i});
  }
  dfs(0, 0);

  vector<int> w(M, 0);
  long long dis = ask(w); // QUERY
  long long ec = dis / A;

  int l = 1, r = mxdep;
  while(l < r){
    int m = (l + r + 1)/2;

    for(int i = 0; i < M; i++) w[i] = 0;
    for(int i = m; i <= mxdep; i++){
      for(auto itr: depth[i]){
        w[topar[itr]] = 1;
      }
    }

    long long check = ask(w);
    if(check == dis) r = m - 1;
    else l = m; 
  }                            // LOG N QUERY

  for(int i = 0; i < M; i++) w[i] = 0;
  for(int i = l; i <= mxdep; i++){
    for(auto itr: depth[i]){
      w[topar[itr]] = 1;
    }
  }

  long long val = ask(w); // QUERY
  bool samedep = 0;
  if(val - dis > (B - A)) samedep = 1;
  int dep2 = l;

  if(samedep){
    vector<int> ans, vis(N);

    for(int dene = 0; dene < 2; dene++){
      vector<int> bsat;
      for(auto itr: depth[dep2]){
        if(!vis[itr]){
          bsat.pb(itr);
        }
      }

      l = 0, r = bsat.size()-1;
      while(l < r){
          int m = (l + r)/2;

          for(int i = 0; i < M; i++) w[i] = 0;
          for(int i = l; i <= m; i++){
            w[topar[bsat[i]]] = 1;
          }

          long long check = ask(w);
          if(check > dis) r = m;
          else l = m + 1;
      }                                 // LOG N QUERY

      ans.pb(bsat[l]);
      vis[bsat[l]] = 1;
    }

    answer(ans[0], ans[1]);
  }
  else{
    int ans2;
    l = 0, r = depth[dep2].size()-1;
    while(l < r){
      int m = (l + r)/2;

      for(int i = 0; i < M; i++) w[i] = 0;
      for(int i = l; i <= m; i++){
        w[topar[depth[dep2][i]]] = 1;
      }
      long long check = ask(w);
      if(check > dis) r = m;
      else l = m + 1;
    }                             // LOG N QUERY
    ans2 = depth[dep2][l];

    vector<int> vis(N);

    bool lcais1 = 0;
    int x = ans2;
    for(int i = 0; i < M; i++) w[i] = 0;
    while(x != 0){
      vis[x] = 1;
      w[topar[x]] = 1;
      x = p[x];
    }
    long long lcacheck = ask(w); // QUERY
    int lcadep;
    if(lcacheck == ec * B) lcais1 = 1;
    else{
      int side2ec = (lcacheck - dis) / (B - A);
      lcadep = dep2 - side2ec;
    }

    if(lcais1){
      int ans1 = ans2;
      for(int i = 0; i < ec; i++) ans1 = p[ans1];
      answer(ans1, ans2);
    }
    else{
      // ec == (dep2 - lcadep) + (dep1 - lcadep) -> ec == dep1 + dep2 - 2*lcadep
      int dep1 = ec - dep2 + 2*lcadep;

      vector<int> bsat;
      for(auto itr: depth[dep1]){
        if(!vis[itr]) bsat.pb(itr);
      }

      l = 0, r = bsat.size()-1;
      while(l < r){
        int m = (l + r)/2;

        for(int i = 0; i < M; i++) w[i] = 0;
        for(int i = l; i <= m; i++){
          w[topar[bsat[i]]] = 1;
        }

        long long check = ask(w);
        if(check > dis) r = m;
        else l = m + 1;
      }                                 // LOG N QUERY

      int ans1 = bsat[l];
      answer(ans1, ans2);
    }
  }
  //answer(0, N - 1); cevabı koy buraya
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 10 ms 1616 KB Output is correct
3 Correct 99 ms 11464 KB Output is correct
4 Correct 94 ms 11760 KB Output is correct
5 Correct 120 ms 11528 KB Output is correct
6 Correct 87 ms 11520 KB Output is correct
7 Correct 84 ms 11752 KB Output is correct
8 Correct 87 ms 11760 KB Output is correct
9 Correct 90 ms 11752 KB Output is correct
10 Correct 97 ms 11572 KB Output is correct
11 Correct 98 ms 12444 KB Output is correct
12 Correct 104 ms 13120 KB Output is correct
13 Correct 96 ms 12744 KB Output is correct
14 Correct 97 ms 12028 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2128 KB Output is correct
2 Correct 20 ms 4176 KB Output is correct
3 Correct 36 ms 6112 KB Output is correct
4 Correct 94 ms 17528 KB Output is correct
5 Correct 90 ms 17752 KB Output is correct
6 Correct 82 ms 17684 KB Output is correct
7 Correct 81 ms 17556 KB Output is correct
8 Correct 90 ms 17620 KB Output is correct
9 Correct 87 ms 17584 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 11 ms 1616 KB Output is correct
3 Correct 73 ms 9196 KB Output is correct
4 Correct 90 ms 11720 KB Output is correct
5 Correct 93 ms 11744 KB Output is correct
6 Correct 95 ms 11756 KB Output is correct
7 Correct 96 ms 11508 KB Output is correct
8 Correct 89 ms 11808 KB Output is correct
9 Correct 92 ms 11760 KB Output is correct
10 Correct 94 ms 11800 KB Output is correct
11 Correct 97 ms 11960 KB Output is correct
12 Correct 99 ms 13424 KB Output is correct
13 Correct 99 ms 12736 KB Output is correct
14 Correct 97 ms 13080 KB Output is correct
15 Correct 86 ms 11752 KB Output is correct
16 Correct 88 ms 11632 KB Output is correct
17 Correct 101 ms 12908 KB Output is correct
18 Correct 105 ms 12488 KB Output is correct
19 Correct 89 ms 11480 KB Output is correct
20 Correct 110 ms 13528 KB Output is correct
21 Correct 81 ms 12612 KB Output is correct
22 Correct 84 ms 12468 KB Output is correct
23 Correct 121 ms 12200 KB Output is correct
24 Correct 97 ms 12984 KB Output is correct
25 Correct 103 ms 16600 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4432 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 4432 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -