oj.uz

답안 #1064976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064976 2024-08-18T20:40:05 Z hyakup 통행료 (IOI18_highway) C++17
5 / 100
 241 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 = 1e5 + 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( 0, 0 );

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

  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() - 1;
  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;
  }
  auto [x, y] = edges[ids[r]];
  int a = (( dist[x] > dist[y]) ? x : y );

  answer( 0, a );
  //
  // 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:68: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]
   68 |   for( int i = 0; i < edges.size(); i++ ){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
      |                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 84 ms 9056 KB Output is correct
4 Correct 82 ms 9056 KB Output is correct
5 Correct 80 ms 9056 KB Output is correct
6 Correct 78 ms 8992 KB Output is correct
7 Correct 93 ms 9012 KB Output is correct
8 Correct 77 ms 9068 KB Output is correct
9 Correct 80 ms 9148 KB Output is correct
10 Correct 73 ms 9056 KB Output is correct
11 Correct 77 ms 9940 KB Output is correct
12 Correct 81 ms 10316 KB Output is correct
13 Correct 82 ms 9964 KB Output is correct
14 Runtime error 82 ms 18940 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4440 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3416 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 241 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 235 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -