oj.uz

Submission #138171

# Submission time Handle Problem Language Result Execution time Memory
138171 2019-07-29T13:49:01 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 386 ms 53196 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) 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 : x[i].s) q[it] = 1;
			sol.pb(x[i]);
		}

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

		ll cur = ask(q);
		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();
		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);
			}
			vector < pair <int, vector <int > > > X;
			for (auto it : edge_tov) {
				X.pb(it);
			}

			int ind = id(X);
			if (0) cerr << dep[V[ind]] << ' ' << dep[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:199:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 1;
              ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 28 ms 6340 KB Output is correct
3 Correct 262 ms 20492 KB Output is correct
4 Correct 244 ms 19756 KB Output is correct
5 Correct 240 ms 20032 KB Output is correct
6 Correct 248 ms 17424 KB Output is correct
7 Correct 246 ms 18816 KB Output is correct
8 Correct 252 ms 21360 KB Output is correct
9 Correct 227 ms 17436 KB Output is correct
10 Correct 239 ms 20424 KB Output is correct
11 Correct 243 ms 13616 KB Output is correct
12 Correct 234 ms 13600 KB Output is correct
13 Correct 250 ms 13348 KB Output is correct
14 Correct 275 ms 12884 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6076 KB Output is correct
2 Correct 37 ms 7024 KB Output is correct
3 Correct 59 ms 8148 KB Output is correct
4 Correct 182 ms 14372 KB Output is correct
5 Correct 190 ms 14392 KB Output is correct
6 Correct 194 ms 13980 KB Output is correct
7 Correct 186 ms 14408 KB Output is correct
8 Correct 206 ms 13976 KB Output is correct
9 Correct 156 ms 14364 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5136 KB Output is correct
2 Correct 22 ms 6512 KB Output is correct
3 Correct 184 ms 15396 KB Output is correct
4 Correct 217 ms 18560 KB Output is correct
5 Correct 198 ms 18120 KB Output is correct
6 Correct 233 ms 20308 KB Output is correct
7 Correct 220 ms 18964 KB Output is correct
8 Correct 213 ms 20204 KB Output is correct
9 Correct 242 ms 18604 KB Output is correct
10 Correct 231 ms 20416 KB Output is correct
11 Correct 228 ms 13556 KB Output is correct
12 Correct 231 ms 13052 KB Output is correct
13 Correct 240 ms 13072 KB Output is correct
14 Correct 249 ms 13148 KB Output is correct
15 Correct 201 ms 19152 KB Output is correct
16 Correct 239 ms 17776 KB Output is correct
17 Correct 320 ms 14096 KB Output is correct
18 Correct 312 ms 13248 KB Output is correct
19 Correct 248 ms 19080 KB Output is correct
20 Correct 255 ms 13144 KB Output is correct
21 Correct 386 ms 52544 KB Output is correct
22 Correct 372 ms 53196 KB Output is correct
23 Correct 288 ms 33684 KB Output is correct
24 Correct 328 ms 34132 KB Output is correct
25 Correct 365 ms 19308 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6452 KB Output is correct
2 Correct 45 ms 7248 KB Output is correct
3 Correct 299 ms 23844 KB Output is correct
4 Correct 335 ms 27520 KB Output is correct
5 Incorrect 329 ms 32452 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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