oj.uz

Submission #138172

# Submission time Handle Problem Language Result Execution time Memory
138172 2019-07-29T13:49:57 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 424 ms 53384 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(rand() % n);
		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 7 ms 5116 KB Output is correct
2 Correct 6 ms 5032 KB Output is correct
3 Correct 6 ms 5032 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5028 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 7 ms 5028 KB Output is correct
10 Correct 7 ms 4984 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 5112 KB Output is correct
2 Correct 30 ms 6648 KB Output is correct
3 Correct 246 ms 19856 KB Output is correct
4 Correct 254 ms 19784 KB Output is correct
5 Correct 242 ms 20440 KB Output is correct
6 Correct 234 ms 16992 KB Output is correct
7 Correct 226 ms 18304 KB Output is correct
8 Correct 260 ms 20604 KB Output is correct
9 Correct 234 ms 19916 KB Output is correct
10 Correct 231 ms 17792 KB Output is correct
11 Correct 272 ms 13640 KB Output is correct
12 Correct 271 ms 13356 KB Output is correct
13 Correct 230 ms 13288 KB Output is correct
14 Correct 286 ms 13024 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6012 KB Output is correct
2 Correct 42 ms 6748 KB Output is correct
3 Correct 59 ms 8120 KB Output is correct
4 Correct 182 ms 13320 KB Output is correct
5 Correct 143 ms 13420 KB Output is correct
6 Correct 209 ms 13088 KB Output is correct
7 Correct 145 ms 13420 KB Output is correct
8 Correct 143 ms 13028 KB Output is correct
9 Correct 111 ms 13412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5092 KB Output is correct
2 Correct 29 ms 6504 KB Output is correct
3 Correct 153 ms 15832 KB Output is correct
4 Correct 227 ms 21220 KB Output is correct
5 Correct 189 ms 17632 KB Output is correct
6 Correct 220 ms 20580 KB Output is correct
7 Correct 221 ms 18816 KB Output is correct
8 Correct 249 ms 20676 KB Output is correct
9 Correct 260 ms 18968 KB Output is correct
10 Correct 271 ms 20564 KB Output is correct
11 Correct 270 ms 13648 KB Output is correct
12 Correct 221 ms 13684 KB Output is correct
13 Correct 244 ms 12984 KB Output is correct
14 Correct 220 ms 13044 KB Output is correct
15 Correct 256 ms 16768 KB Output is correct
16 Correct 226 ms 16368 KB Output is correct
17 Correct 216 ms 13428 KB Output is correct
18 Correct 244 ms 13216 KB Output is correct
19 Correct 255 ms 19164 KB Output is correct
20 Correct 241 ms 13008 KB Output is correct
21 Correct 424 ms 52904 KB Output is correct
22 Correct 355 ms 53384 KB Output is correct
23 Correct 311 ms 33624 KB Output is correct
24 Correct 278 ms 34088 KB Output is correct
25 Correct 317 ms 18824 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6592 KB Output is correct
2 Incorrect 38 ms 7268 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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