Submission #138274

#	Time	Username	Problem	Language	Result	Execution time	Memory
138274		RockyB	Highway Tolls (IOI18_highway)	C++17	0 / 100	44 ms	4024 KiB

highway

// In The Name Of God

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define f first
#define s second

#define pb push_back
#define pp pop_back

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define nl '\n'
#define ioi exit(0);

typedef long long ll;

const int MAX_N = (int)1e5 + 7;
const int INF = (int)1e9 + 7;
	

int n, m, A, B;

vector <int> V, U;
vector < pair <int, int > > g[MAX_N];

namespace Tree {
	int depth;
	ll min_len;
	int dep[MAX_N];

	vector <int> e;

	bool was[MAX_N];

	void bfs(int v = 0, int p = -1, int lvl = 0) {
		dep[v] = 0;
		was[v] = 1;
		queue <int> q;
		q.push(v);

		while (sz(q)) {
			int x = q.front();
			q.pop();
			for (auto to : g[x]) {
				if (!was[to.f]) {
					dep[to.f] = dep[x] + 1;
					was[to.f] =  1;
					q.push(to.f);
				}
			}
		}
	}
	int GetT(const vector <int> &x) {
		if (sz(x) == 1) return x[0];
		int mid = sz(x) / 2;

		vector <int> q(m, 0), sol;

		rep(i, 0, mid - 1) {
			for (auto to : g[x[i]]) q[to.s] = 1;
			sol.pb(x[i]);
		}

		// if (0) cerr << sz(x) << endl;
		assert(sz(sol));

		ll cur = ask(q);
		if (cur > min_len) return GetT(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return GetT(on);
	}
	void solve(int S = 0) {
		{ 
			vector <int> q(m, 0);
			min_len = ask(q);
			depth = min_len / A;
		}
		bfs(S);
		rep(i, 0, n - 1) {
			if (dep[i] == depth) {
				e.pb(i);
			}
		}
		int T = GetT(e);
		cerr << S << ' ' << T << endl;
		answer(S, T);
	}
}
namespace FindS {
	int dist;
	int dep[MAX_N];
	bool was[MAX_N];

	void bfs(int v = 0) {
		queue <int> q;
		memset(was, 0, sizeof(was));
		dep[v] = 0;
		was[v] = 1;
		q.push(v);
		while (sz(q)) {
			int x = q.front();
			q.pop();
			for (auto to : g[x]) {
				if (!was[to.f]) {
					dep[to.f] = dep[x] + 1;
					was[to.f] = 1;
					q.push(to.f);
				}
			}
		}
	}
	int FindV(const vector <int> &x) {
		if (sz(x) == 1) return x[0];
		int mid = sz(x) / 2;

		vector <int> q(m, 0), sol;

		rep(i, 0, mid - 1) {
			for (auto to : g[x[i]]) q[to.s] = 1;
			sol.pb(x[i]);
		}

		// if (0) cerr << sz(x) << endl;
		assert(sz(sol));

		ll cur = ask(q);
		if (cur > (ll)dist * A) return FindV(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return FindV(on);
	}
	int GetS() {
		{ 
			vector <int> q(m, 0);
			dist = ask(q) / A;
		}
		// dist of path 
		int C = -1;
		{
			bfs();
			int l = 0, r = n, res = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				vector <int> q(m, 0);
				rep(i, 0, n - 1) if (dep[i] <= mid) for (auto it : g[i]) q[it.s] = 1;
				ll cur = ask(q);
				if (cur > (ll)dist * A) res = mid, r = mid - 1;
				else l = mid + 1;
			}
			assert(res != -1);
			vector <int> x;
			rep(i, 0, n - 1) if (dep[i] == res) x.pb(i);
			C = FindV(x);
		}
		// Found dist to first vertex on path S, T and that vertex
		int S = -1;
		{
			bfs(C);
			// cerr << "Start -> " << C << endl;
			// rep(i, 0, n - 1) cerr << dep[i] << ' ' << i << endl;
			int l = 0, r = n, res = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				vector <int> q(m, 0);
				rep(i, 0, n - 1) if (dep[i] <= mid) for (auto it : g[i]) if (dep[it.f] <= mid) q[it.s] = 1;
				ll cur = ask(q);
				if (cur == (ll)dist * B) res = mid, r = mid - 1;
				else l = mid + 1;
			}
			assert(res != -1);
			vector <int> x;
			rep(i, 0, n - 1) if (dep[i] == res) x.pb(i);
			// for (auto it : x) cerr << it << ' ';
			
			S = FindV(x);
		}
		// Found S
		// cerr << S << endl;
		return S;
	}
}
/*namespace FindS {

	int dist;
	int dep[MAX_N];
	vector <int> edges[MAX_N];

	bool was[MAX_N];
	void bfs(int v = 0, int p = -1, int lvl = 0) {
		dep[v] = 0;
		was[v] = 1;
		queue <int> q;
		q.push(v);
		while (sz(q)) {
			int x = q.front();
			q.pop();
			for (auto to : g[x]) {
				if (!was[to.f]) {
					dep[to.f] = dep[x] + 1;
					was[to.f] = 1;
					q.push(to.f);
				}
			}
		}
	}
	int id1(const vector <int> &x) {
		if (sz(x) == 1) return x[0];
		int mid = sz(x) / 2;

		vector <int> q(m, 0), sol;

		rep(i, 0, mid - 1) {
			q[x[i]] = 1;
			sol.pb(x[i]);
		}

		// if (0) cerr << sz(x) << endl;
		assert(sz(sol));

		ll cur = ask(q);
		if (cur > dist * A) return id1(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id1(on);
	}

	int NeedLen;
	int S = -1;
	bool check(int x) {
		vector <int> q(m, 0);
		for (auto to : g[x]) q[to.s] = 1;
		return ask(q) == (ll)(dist - 1) * A + B; 
	}
	int id(vector < pair <int, vector <int> > > x) {
		if (sz(x) == 1) {
			if (check(x[0].f)) {
				S = x[0].f;
				cerr << "X[0].f is optimal" << ' ' << x[0].f << ' ' << check(x[0].f) << endl;
			}
			if (0) cerr << " -> " << x[0].f << endl;
			vector <int> ind;
			for (auto it : g[x[0].f]) {
				// ind.pb(it);
				// cerr << min(dep[x[0].f], dep[it.f]) << ' ' << it.s << ' ' << NeedLen << endl;
				if (min(dep[x[0].f], dep[it.f]) == NeedLen) ind.pb(it.s);
			}
			// ioi
			return id1(ind);
		}
		int mid = sz(x) / 2;

		vector <int> q(m, 0);
		vector < pair <int, vector <int> > > sol;

		rep(i, 0, mid - 1) {
			for (auto it : g[x[i].f]) q[it.s] = 1;
			sol.pb(x[i]);
		}

		// if (0) cerr << sz(x) << endl;
		assert(sz(sol));

		ll cur = ask(q);
		// cerr << sz(sol) << ' ' << sol[0].f << ' ' << cur << endl;
		if (cur > (ll)dist * A) return id(sol);

		vector < pair <int, vector <int> > > on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id(on);
	}
	int GetS() {
		{ 
			vector <int> q(m, 0);
			dist = ask(q) / A;
		}
		// dist of path 
		bfs(0);
		rep(i, 0, n) {
			for (auto to : g[i]) {
				edges[min(dep[i], dep[to.f])].pb(to.s);
			}
		}

		int l = 0, r = n, res = -1;
		while (l <= r) {
			int mid = l + r >> 1;
			vector <int> q(m, 0);
			rep(i, 0, mid) for (auto ind : edges[i]) q[ind] = 1;
			ll cur = ask(q);
			if (cur == (ll)dist * B) res = mid, r = mid - 1;
			else l = mid + 1;
		}
		if (res == -1) {
			if (0) cerr << "DIDN't FIND DEPTH of S" << endl;
		}
		assert(res != -1);
		// found depth of S
		{
			map <int, vector <int > > edge_tov;
			for (auto i : edges[res]) {
				int x = V[i], y = U[i];
				if (dep[x] > dep[y]) swap(x, y);
				edge_tov[y].pb(i);
				// cerr << V[i] << ' ' << U[i] << " -> " << y << endl;
				if (dep[x] == dep[y]) edge_tov[x].pb(i);
			}
			vector < pair <int, vector <int > > > X;
			for (auto it : edge_tov) {
				if (0) cerr << it.f << endl;
				X.pb(it);
			}
			NeedLen = res;
			int ind = id(X);
			cerr << S << endl;
			if (S != -1) 
			// cerr <<
			// cerr << ind << endl;
			if (0) cerr << V[ind] << ' ' << U[ind] << endl;
			if (check(V[ind])) return V[ind];
			return U[ind];
		}
		// found S
		if (0) cerr << "DIDN'T FIND S" << endl;
		assert(0);
	}	
}*/

void find_pair(int N, vector<int> _U, vector<int> _V, int _A, int _B) {
  n = N;
  m = sz(_U);
  A = _A;
  B = _B;
  V = _V;
  U = _U;
  rep(i, 0, m - 1) {
  	g[V[i]].pb({U[i], i});
  	g[U[i]].pb({V[i], i});
  }
  // copy finished
  int S = FindS :: GetS();
  if (0) cerr << S << endl;
  Tree :: solve(S);
  return;
  answer(0, N - 1);
}

Compilation message (stderr)

highway.cpp: In function 'int FindS::GetS()':
highway.cpp:154:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
highway.cpp:174:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 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