oj.uz

Submission #592795

# Submission time Handle Problem Language Result Execution time Memory
592795 2022-07-09T15:45:55 Z farhan132 Highway Tolls (IOI18_highway) C++17
12 / 100
 184 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back

const ll N = 1e5 + 5;

vector < ii > v[N];
ii edge[N]; ll in[N]; ll par[N];
ll n, m;
vector < ll > all;

void dfs(ll s, ll p){
  par[s] = p;
  for(auto [u, i] : v[s]){
    if(u - p){
      dfs(u, s);
      in[i] = all.size();
      all.pb(i);
      edge[i] = {s, u};
    }
  }
  return;
}
ll query(ll l, ll r){
  vector < int > w(m, 0);
  if(r == -1) return ask(w);
  for(ll i = l; i <= r; i++) w[all[i]] = 1;
  return ask(w);
}
vector < ll > collect;
void DFS(ll s, ll p){
  for(auto [u, i] : v[s]){
    if(u - p){
      DFS(u, s);
      collect.pb(i);
    }
  }
  return;
}

void find_pair(int _n, std::vector<int> U, std::vector<int> V, int A, int B) {
  n = _n, m = U.size();
  for(ll i = 0; i < m; i++){
    ll x = V[i], y = U[i];
    v[x].pb({y, i});
    v[y].pb({x, i});
  }
  dfs(0, -1);
  ll cost = query(0, -1);
  ll lo = 0, hg = m - 1;
  ll X = 0, root = 0, Y = 0;
  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(0, mid);
    if(k == cost){
      lo = mid + 1;
    }else{
      X = mid;
      hg = mid - 1;
    }
  }
  lo = 0, hg = m - 1;

  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(mid, m-1);

    if(k == cost){
       hg = mid - 1;
    }else{

      root = mid;
      lo = mid + 1;
    }
  }
  //return;
  ll _X = edge[all[X]].ss;
  ll _R = edge[all[root]].ff;
  DFS(edge[all[root]].ss, _R);
  collect.pb(root);
  sort(collect.begin(), collect.end());
  ll L = collect[0], R = collect.back();
  lo = L, hg = R;
  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(L, mid);
    if(k == cost){
      lo = mid + 1;
    }else{
      hg = mid - 1;
      Y = mid;
    }
  }


  ll _Y = edge[all[Y]].ss;
  int S,T;
  if(_X == _Y) S = _X, T = _R;
  else S = _X, T = _Y;
 // cout << _X << ' ' << _R << ' ' << _Y << '\n';
  answer(S, T);
  return;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2768 KB Output is correct
2 Correct 13 ms 3992 KB Output is correct
3 Correct 132 ms 14112 KB Output is correct
4 Correct 144 ms 14044 KB Output is correct
5 Correct 150 ms 14056 KB Output is correct
6 Correct 172 ms 14156 KB Output is correct
7 Correct 178 ms 14096 KB Output is correct
8 Correct 162 ms 14064 KB Output is correct
9 Correct 184 ms 14052 KB Output is correct
10 Correct 138 ms 14120 KB Output is correct
11 Correct 134 ms 15844 KB Output is correct
12 Correct 156 ms 17564 KB Output is correct
13 Correct 180 ms 16808 KB Output is correct
14 Correct 173 ms 14908 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4936 KB Output is correct
2 Correct 32 ms 7092 KB Output is correct
3 Incorrect 46 ms 9204 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2768 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -