Submission #1065046

#TimeUsernameProblemLanguageResultExecution timeMemory
1065046hyakupHighway Tolls (IOI18_highway)C++17
0 / 100
235 ms262144 KiB
#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( 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 ); if( ask( arestas ) == distancia*B ) r = mid; else l = mid + 1; } int nivel_a = r; vector<int> ids; for( int i = 0; i < edges.size(); i++ ){ auto [x, y] = edges[i]; if( max( dist[x], dist[y] ) == nivel_a ) ids.push_back(i); } marca( n - 1 ); 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 ); vector<bool> ancestral(n); for( int i = 0, aux = a; i <= distancia; i++, aux = pai[aux] ) ancestral[aux] = true; 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 == 0 ){ answer( a, p2 ); } else{ ids.clear(); for( int i = 0; i < edges.size(); i++ ){ auto [x, y] = edges[i]; if( !( ancestral[x] && ancestral[y] ) && max( dist[x], dist[y] ) == nivel_b ) ids.push_back(i); } marca( n - 1 ); 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 b = (( dist[x] > dist[y]) ? x : y ); answer( a, b ); } }

Compilation message (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:66: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]
   66 |   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 ));
      |                     ~~^~~~~~~~~~~~
highway.cpp:102: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]
  102 |     for( int i = 0; i < edges.size(); i++ ){
      |                     ~~^~~~~~~~~~~~~~
highway.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |       for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
      |                       ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...