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
51 / 100
 202 ms 54948 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);
}

Compilation message

highway.cpp: In function 'int FindS::GetS()':
highway.cpp:203:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  203 |    int mid = l + r >> 1;
      |              ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5968 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 3 ms 5968 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 2 ms 5968 KB Output is correct
6 Correct 3 ms 5968 KB Output is correct
7 Correct 2 ms 5968 KB Output is correct
8 Correct 3 ms 6224 KB Output is correct
9 Correct 2 ms 5964 KB Output is correct
10 Correct 3 ms 5968 KB Output is correct
11 Correct 3 ms 5968 KB Output is correct
12 Correct 3 ms 6032 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5968 KB Output is correct
2 Correct 13 ms 7248 KB Output is correct
3 Correct 141 ms 20964 KB Output is correct
4 Correct 138 ms 20280 KB Output is correct
5 Correct 120 ms 20620 KB Output is correct
6 Correct 118 ms 18072 KB Output is correct
7 Correct 138 ms 19480 KB Output is correct
8 Correct 125 ms 21832 KB Output is correct
9 Correct 120 ms 17916 KB Output is correct
10 Correct 133 ms 20808 KB Output is correct
11 Correct 113 ms 13744 KB Output is correct
12 Correct 117 ms 13540 KB Output is correct
13 Correct 133 ms 13784 KB Output is correct
14 Correct 124 ms 13044 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6736 KB Output is correct
2 Correct 26 ms 7708 KB Output is correct
3 Correct 33 ms 8744 KB Output is correct
4 Correct 111 ms 14356 KB Output is correct
5 Correct 84 ms 14456 KB Output is correct
6 Correct 86 ms 14204 KB Output is correct
7 Correct 87 ms 14488 KB Output is correct
8 Correct 85 ms 14212 KB Output is correct
9 Correct 85 ms 14556 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5968 KB Output is correct
2 Correct 13 ms 7336 KB Output is correct
3 Correct 85 ms 15920 KB Output is correct
4 Correct 112 ms 19200 KB Output is correct
5 Correct 103 ms 18580 KB Output is correct
6 Correct 117 ms 20828 KB Output is correct
7 Correct 110 ms 19584 KB Output is correct
8 Correct 111 ms 20724 KB Output is correct
9 Correct 126 ms 19512 KB Output is correct
10 Correct 127 ms 21064 KB Output is correct
11 Correct 127 ms 13920 KB Output is correct
12 Correct 135 ms 13564 KB Output is correct
13 Correct 111 ms 13024 KB Output is correct
14 Correct 117 ms 13276 KB Output is correct
15 Correct 129 ms 19780 KB Output is correct
16 Correct 119 ms 18484 KB Output is correct
17 Correct 138 ms 14468 KB Output is correct
18 Correct 125 ms 13488 KB Output is correct
19 Correct 123 ms 19912 KB Output is correct
20 Correct 108 ms 13308 KB Output is correct
21 Correct 196 ms 54332 KB Output is correct
22 Correct 202 ms 54948 KB Output is correct
23 Correct 158 ms 34772 KB Output is correct
24 Correct 145 ms 35452 KB Output is correct
25 Correct 150 ms 20032 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 7388 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 7888 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -