oj.uz

Submission #138185

# Submission time Handle Problem Language Result Execution time Memory
138185 2019-07-29T14:24:58 Z RockyB Highway Tolls (IOI18_highway) C++17
Evaluating test 4-14
 279 ms 21444 KB 
// 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);
					if (dep[x] + 1 == depth) {
						// e.pb(to.s);
					}
				}
			}
		}
		/// -------------------------
		/*return;
		for (auto to : g[v]) {
			if (to.f != p) {
				dfs(to.f, v, lvl + 1);
				if (lvl + 1 == depth) {
					e.pb(to.s);
				}
			}
		}*/
	}
	int id(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 > min_len) return id(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id(on);
	}
	void solve(int S = 0) {
		// if (n != m + 1) return;

		{ 
			vector <int> q(m, 0);
			min_len = ask(q);
			depth = min_len / A;
		}
		bfs(S);
		rep(i, 0, n) {
			for (auto to : g[i]) {
				if (min(dep[i], dep[to.f]) + 1 == depth) {
					e.pb(to.s);
				}
			}
		}
		int ed = id(e);
		rep(i, 0, n - 1) {
			for (auto it : g[i]) {
				if (it.s == ed) {
					if (dep[i] > dep[it.f]) answer(S, i);
					else answer(S, it.f);
					return;
				}	
			}
		}
		assert(0);
	}
}

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);
				}
			}
		}
		// ------------------------
		/*return;
		for (auto to : g[v]) {
			if (to.f != p) {
				dfs(to.f, v, lvl + 1);
				edges[lvl].pb(to.s);
			}
		}*/
	}
	int id(vector < pair <int, vector <int> > > x) {
		if (sz(x) == 1) {
			if (0) cerr << " -> " << x[0].f << endl;
			return x[0].s[0];
		}
		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);
	}
	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 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) {
				// cerr << it.f << endl;
				X.pb(it);
			}

			int ind = id(X);
			// cerr <<
			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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5036 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5032 KB Output is correct
9 Correct 6 ms 5040 KB Output is correct
10 Correct 7 ms 4936 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5036 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 24 ms 6388 KB Output is correct
3 Correct 237 ms 20468 KB Output is correct
4 Correct 265 ms 19724 KB Output is correct
5 Correct 238 ms 20092 KB Output is correct
6 Correct 237 ms 17336 KB Output is correct
7 Correct 237 ms 18912 KB Output is correct
8 Correct 276 ms 21444 KB Output is correct
9 Correct 232 ms 17488 KB Output is correct
10 Correct 260 ms 20332 KB Output is correct
11 Correct 233 ms 13644 KB Output is correct
12 Correct 279 ms 13508 KB Output is correct
13 Correct 247 ms 13316 KB Output is correct
14 Correct 254 ms 12888 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6008 KB Output is correct
2 Correct 63 ms 7100 KB Output is correct
3 Correct 66 ms 8140 KB Output is correct
4 Correct 177 ms 14264 KB Output is correct
5 Correct 159 ms 14348 KB Output is correct
6 Correct 213 ms 13968 KB Output is correct
7 Correct 191 ms 14348 KB Output is correct
8 Correct 194 ms 13972 KB Output is correct
9 Correct 192 ms 14312 KB Output is correct