Submission #104707

#	Time	Username	Problem	Language	Result	Execution time	Memory
104707		turbat	Highway Tolls (IOI18_highway)	C++14	0 / 100	33 ms	5624 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using pii = pair <int, int>;
using vi = vector <int>;
#define N 200005
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define ll long long
int deep[N], cnt, flat[N], len,  curdeep;
vector <pii> edg[N];
pii parent[N];
bool vis[N];
void dfs(int u){
	vis[u] = 1;
	flat[cnt++] = u;
	for (pii v : edg[u])
		if (vis[v.F]){
			dfs(v.F);
			parent[v.F] = mp(u, v.S);			
		}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  	int M = U.size();
 	vi v(M);
 	ll maxdist, dist, mindist;
 	for (int i = 0;i < M;i++) v[i] = 1;
 	maxdist = ask(v);
 	for (int i = 0;i < M;i++) v[i] = 0;
 	for (int i = 0;i < M;i++){
 		edg[U[i]].pb(mp(V[i], i));
 		edg[V[i]].pb(mp(U[i], i));
 	}
 	dfs(1);
 	int l = 1, r = n - 1, mid;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	for (int i = 0;i < M;i++) v[i] = 0;
 	int s = flat[l];
 	r = l;
 	l = 2;
 	while (l != r){
 		mid = (l + r + 1) / 2;
 		for (int i = mid;i <= r;i++)
 			v[parent[flat[i]].S] = 1;
 		if (dist < maxdist)	r = mid - 1;
 		else{
 			l = mid;
	 		for (int i = mid;i <= r;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	int t = parent[flat[l]].F;
 	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:28:21: warning: unused variable 'mindist' [-Wunused-variable]
   ll maxdist, dist, mindist;
                     ^~~~~~~
highway.cpp:58:4: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if (dist < maxdist) r = mid - 1;
    ^~

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