oj.uz

Submission #1064970

# Submission time Handle Problem Language Result Execution time Memory
1064970 2024-08-18T20:30:46 Z hyakup Highway Tolls (IOI18_highway) C++17
5 / 100
 225 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 9e4 + 10;
vector<pii> edges;
vector<int> adj[maxn], pai( maxn ), dist( maxn ), arestas ;

pii dfs( int cur, int last ){
  pii resp( 0, cur );
  pai[cur] = last;
  for( auto viz : adj[cur] ) if( viz != last ){
    auto [d, id] = dfs( viz, cur );
    resp = max( resp, pii( d + 1, id ) );
  }
  return resp;
}

void dfsInit( int cur, int last ){
  pai[cur] = last;
  for( int viz : adj[cur] ) if( viz != last ){
    dist[viz] = dist[cur] + 1;
    dfsInit( viz, cur );
  }
}

void marca( int k ){
  for( int i = 0; i < edges.size(); i++ ){
    auto [a, b] = edges[i];
    arestas[i] = (int)(max(dist[a], dist[b]) <= k );
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  int m = U.size();
  int n = N;
  for( int i = 0; i < m; i++ ){
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
    edges.push_back({ U[i], V[i] });
  }

  int p1 = dfs( 0, 0 ).second;
  auto [diam, p2] = dfs( p1, p1 );
  for( int x = 0; x < diam/2; x++ ) p2 = pai[p2];

  dfsInit( p2, p2 );

  arestas.resize(m);
  ll distancia = ask(arestas)/A;

  int l = 0, r = n - 1;
  while( l < r ){
    int mid = ( l + r )/2;
    marca( mid );
    int aux = ask( arestas );
    if( aux == distancia*B ) r = mid;
    else l = mid + 1;
  }

  int nivel_a = r;

  vector<int> ids;
  for( int i = 0; i < edges.size(); i++ ){
    auto [a, b] = edges[i];
    if( max( dist[a], dist[b] ) == nivel_a ) ids.push_back(i);
  }

  l = 0, r = ids.size();
  while( l < r ){
    int mid = ( l + r )/2;
    for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
    if( ask( arestas ) < distancia*B ) r = mid;
    else l = mid + 1;
  }

  int a = (( dist[edges[ids[r]].first] > dist[edges[ids[r]].second]) ?edges[ids[r]].first : edges[ids[r]].second );

  vector<bool> ancestral(N);
  int aux = a;
  while( true ){
    ancestral[aux] = true;
    if( aux == pai[aux] ) break;
    aux = pai[aux];
  }

  l = max( 0LL, nivel_a - distancia ), r = nivel_a;

  while( l < r ){
    int mid = ( l + r )/2;
    marca( mid );
    if( ask( arestas ) == distancia*B - 1LL*( nivel_a - mid )*(B - A)) r = mid;
    else l = mid + 1;
  }

  int nivel_b = r;

  if( nivel_b == nivel_a - distancia ){
    int b = a;
    for( int i = 0; i < distancia; i++ ) b = pai[b];
    answer( a, b );
  }
  else{
    ids.clear();
    for( int i = 0; i < edges.size(); i++ ){
      auto [a, b] = edges[i];
      if( !(ancestral[a] && ancestral[b] ) && max( dist[a], dist[b] ) == nivel_b ) ids.push_back(i);
    }

    marca( n - 1 );
    l = 0, r = ids.size();
    while( l < r ){
      int mid = ( l + r )/2;
      for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
      if( ask( arestas ) < distancia*B ) r = mid;
      else l = mid + 1;
    }

    int b = (( dist[edges[ids[r]].first] > dist[edges[ids[r]].second]) ?edges[ids[r]].first : edges[ids[r]].second );
    answer( a, b );
  }

}

Compilation message

highway.cpp: In function 'void marca(int)':
highway.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for( int i = 0; i < edges.size(); i++ ){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for( int i = 0; i < edges.size(); i++ ){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
      |                     ~~^~~~~~~~~~~~
highway.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for( int i = 0; i < edges.size(); i++ ){
      |                     ~~^~~~~~~~~~~~~~
highway.cpp:117:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |       for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
      |                       ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 9 ms 3672 KB Output is correct
3 Correct 92 ms 8980 KB Output is correct
4 Correct 102 ms 8768 KB Output is correct
5 Correct 95 ms 8752 KB Output is correct
6 Correct 91 ms 8744 KB Output is correct
7 Correct 104 ms 8748 KB Output is correct
8 Correct 106 ms 8760 KB Output is correct
9 Correct 84 ms 8752 KB Output is correct
10 Correct 84 ms 8840 KB Output is correct
11 Correct 96 ms 9980 KB Output is correct
12 Correct 99 ms 10428 KB Output is correct
13 Correct 97 ms 10156 KB Output is correct
14 Runtime error 86 ms 19624 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4184 KB Output is correct
2 Correct 16 ms 5332 KB Output is correct
3 Correct 23 ms 6356 KB Output is correct
4 Correct 70 ms 12740 KB Output is correct
5 Correct 67 ms 12740 KB Output is correct
6 Correct 73 ms 12768 KB Output is correct
7 Correct 66 ms 12760 KB Output is correct
8 Correct 68 ms 13008 KB Output is correct
9 Runtime error 81 ms 25540 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 10 ms 3896 KB Output is correct
3 Correct 70 ms 7512 KB Output is correct
4 Correct 87 ms 8752 KB Output is correct
5 Correct 96 ms 8704 KB Output is correct
6 Correct 85 ms 8760 KB Output is correct
7 Correct 87 ms 8744 KB Output is correct
8 Correct 93 ms 8748 KB Output is correct
9 Runtime error 86 ms 17060 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 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 225 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -