Submission #126023

#	Time	Username	Problem	Language	Result	Execution time	Memory
126023		sebinkim	Highway Tolls (IOI18_highway)	C++14	100 / 100	458 ms	11232 KiB

highway

#include <bits/stdc++.h>

#include "highway.h"

using namespace std;

typedef long long ll;

vector <int> G[101010], X, Y;
queue <int> Q;
int D1[101010], N1[101010], P1[101010];
int D2[101010], N2[101010], P2[101010];
int cnt;

void bfs(int p, int *D, int *N, int *P)
{
	cnt = 0; Q.push(p);
	N[p] = ++cnt;
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		for(int &t: G[p]){
			if(!N[t]){
				P[t] = p; D[t] = D[p] + 1;
				N[t] = ++cnt;
				Q.push(t);
			}
		}
	}
}
void find_pair(int n, vector <int> U, vector <int> V, int a, int b)
{
	int m = U.size();
	vector <int> W(m, 0);
	int i, k, t, x, u, v, s, e;
	
	for(i=0; i<m; i++){
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	
	k = ask(W) / a;
	
	for(s=0, e=m-1; s<=e; ){
		for(i=0; i<m; i++){
			if(i <= (s + e >> 1)) W[i] = 1;
			else W[i] = 0;
		}
		if(ask(W) != (ll)a * k) e = (s + e >> 1) - 1;
		else s = (s + e >> 1) + 1;
	}
	
	t = e + 1;
	bfs(U[t], D1, N1, P1);
	bfs(V[t], D2, N2, P2);
	
	for(i=0; i<n; i++){
		if(D1[i] < D2[i]) X.push_back(i);
		else if(D1[i] > D2[i]) Y.push_back(i);
	}
	
	sort(X.begin(), X.end(), [&](int &a, int &b){
		return N1[a] < N1[b];
	});
	
	sort(Y.begin(), Y.end(), [&](int &a, int &b){
		return N2[a] < N2[b];
	});
	
	for(s=0, e=X.size()-1; s<=e; ){
		x = N1[X[s + e >> 1]];
		for(i=0; i<m; i++){
			if(i == t) W[i] = 0;
			else if(D1[U[i]] < D2[U[i]] && D1[V[i]] < D2[V[i]]){
				if(P1[U[i]] != V[i] && P1[V[i]] != U[i]) W[i] = 1;
				else if(max(N1[U[i]], N1[V[i]]) > x) W[i] = 1;
				else W[i] = 0;
			}
			else if(D1[U[i]] > D2[U[i]] && D1[V[i]] > D2[V[i]]) W[i] = 0;
			else W[i] = 1;
		}
		if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
		else e = (s + e >> 1) - 1;
	}
	
	u = X[e + 1];
	
	for(s=0, e=Y.size()-1; s<=e; ){
		x = N2[Y[s + e >> 1]];
		for(i=0; i<m; i++){
			if(i == t) W[i] = 0;
			else if(D2[U[i]] < D1[U[i]] && D2[V[i]] < D1[V[i]]){
				if(P2[U[i]] != V[i] && P2[V[i]] != U[i]) W[i] = 1;
				else if(max(N2[U[i]], N2[V[i]]) > x) W[i] = 1;
				else W[i] = 0;
			}
			else if(D2[U[i]] > D1[U[i]] && D2[V[i]] > D1[V[i]]) W[i] = 0;
			else W[i] = 1;
		}
		if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
		else e = (s + e >> 1) - 1;
	}
	
	v = Y[e + 1];
	
	answer(u, v);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(i <= (s + e >> 1)) W[i] = 1;
             ~~^~~
highway.cpp:49:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) e = (s + e >> 1) - 1;
                                ~~^~~
highway.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else s = (s + e >> 1) + 1;
             ~~^~~
highway.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = N1[X[s + e >> 1]];
            ~~^~~
highway.cpp:82:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:83:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s + e >> 1) - 1;
             ~~^~~
highway.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = N2[Y[s + e >> 1]];
            ~~^~~
highway.cpp:100:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:101:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s + e >> 1) - 1;
             ~~^~~

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