제출 #1064978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064978		hyakup	통행료 (IOI18_highway)	C++17	12 / 100	247 ms	262144 KiB

highway

#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 );
    // bug(i);
    // bug(arestas[i]);
  }
}

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 );
    ll aux = ask( arestas );
    if( aux == distancia*B ) r = mid;
    else l = mid + 1;
  }
  int nivel_a = r;
  // bug(nivel_a);

  marca( n - 1 );

  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 );
  // }

}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31