oj.uz

Submission #1017979

# Submission time Handle Problem Language Result Execution time Memory
1017979 2024-07-09T12:14:26 Z mindiyak Highway Tolls (IOI18_highway) C++17
12 / 100
 274 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<long> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vector<pi>> vvpi;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;

ll N,M;
vvpi paths;
vi dist,parent,highway;
ll none = 0;

ll fill_with(vi ways){
  vi quest(M,0);
  for(int i:ways)quest[i] = 1;
  int64_t val = ask(quest);
  return val;
}

void dfs(int pos,int cost,int prev,int hway){
  dist[pos] = cost;
  parent[pos] = prev;
  highway[pos] = hway;
  for(auto a:paths[pos]){
    if(a.F == prev)continue;
    dfs(a.F,cost+1,pos,a.S);
  }
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  N = n;M = N-1;
  paths = vvpi(N,vpi());
  dist = vi(N,-1);
  highway = vi(N,-1);
  parent = vi(N,-1);
  FOR(i,0,M){
    paths[U[i]].pb({V[i],i});
    paths[V[i]].pb({U[i],i});
  }
  dfs(0,0,-1,-1);

  vi ends;
  ll length = fill_with(ends)/A;
  FOR(i,0,N){
    if(dist[i] != length)continue;
    ends.pb(i);
  }

  int l = 0,r = ends.size()-1;
  while(l<r){
    int mid = (l+r)/2;
    vi temp;
    FOR(i,0,mid+1){
      temp.pb(highway[ends[i]]);
    }
    ll counter = fill_with(temp) - (length*A);
    if(counter>0){
      r = mid;
    }else{
      l = mid + 1;
    }
  }

  // cout << ends[l] << endl;
  answer(0,ends[l]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1276 KB Output is correct
3 Correct 66 ms 8724 KB Output is correct
4 Correct 78 ms 8704 KB Output is correct
5 Correct 74 ms 8840 KB Output is correct
6 Correct 60 ms 8688 KB Output is correct
7 Correct 70 ms 8720 KB Output is correct
8 Correct 66 ms 8848 KB Output is correct
9 Correct 63 ms 8720 KB Output is correct
10 Correct 60 ms 8692 KB Output is correct
11 Correct 64 ms 9060 KB Output is correct
12 Correct 60 ms 9564 KB Output is correct
13 Correct 63 ms 9220 KB Output is correct
14 Correct 67 ms 8796 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 271 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 274 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -