oj.uz

Submission #138133

# Submission time Handle Problem Language Result Execution time Memory
138133 2019-07-29T11:57:22 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 353 ms 19764 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 < pair <int, int > > g[MAX_N];

namespace Tree {
	// We suppose that S or T is 0
	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(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 > (ll)dist * A) return id(sol);

		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();
		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
		{
			int ind = id(edges[res]);
			rep(i, 0, n - 1) {
				for (auto to : g[i]) {
					if (to.s == ind) {
						if (dep[i] > dep[to.f]) return i;
						return to.f;
					}
				}
			}
		}
		// 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;
  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:192: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 6 ms 5044 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5116 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 6 ms 5032 KB Output is correct
7 Correct 6 ms 5040 KB Output is correct
8 Correct 6 ms 5032 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5116 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5116 KB Output is correct
2 Correct 27 ms 6028 KB Output is correct
3 Correct 228 ms 16828 KB Output is correct
4 Correct 222 ms 16292 KB Output is correct
5 Correct 232 ms 16756 KB Output is correct
6 Correct 219 ms 15920 KB Output is correct
7 Correct 222 ms 16788 KB Output is correct
8 Correct 245 ms 16576 KB Output is correct
9 Correct 229 ms 16872 KB Output is correct
10 Correct 240 ms 16560 KB Output is correct
11 Correct 250 ms 12916 KB Output is correct
12 Correct 247 ms 12852 KB Output is correct
13 Correct 242 ms 12628 KB Output is correct
14 Correct 264 ms 12432 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5952 KB Output is correct
2 Correct 38 ms 6844 KB Output is correct
3 Correct 56 ms 7908 KB Output is correct
4 Correct 162 ms 13592 KB Output is correct
5 Correct 165 ms 13596 KB Output is correct
6 Correct 180 ms 13332 KB Output is correct
7 Correct 187 ms 13660 KB Output is correct
8 Correct 179 ms 13316 KB Output is correct
9 Correct 175 ms 13580 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 50 ms 6212 KB Output is correct
3 Correct 186 ms 13372 KB Output is correct
4 Correct 235 ms 16020 KB Output is correct
5 Correct 218 ms 15844 KB Output is correct
6 Correct 229 ms 16128 KB Output is correct
7 Correct 213 ms 16200 KB Output is correct
8 Correct 236 ms 16244 KB Output is correct
9 Correct 248 ms 16716 KB Output is correct
10 Correct 217 ms 16816 KB Output is correct
11 Correct 258 ms 12860 KB Output is correct
12 Correct 275 ms 12628 KB Output is correct
13 Correct 262 ms 12312 KB Output is correct
14 Correct 265 ms 12436 KB Output is correct
15 Correct 239 ms 16184 KB Output is correct
16 Correct 193 ms 15844 KB Output is correct
17 Correct 263 ms 13364 KB Output is correct
18 Correct 245 ms 12732 KB Output is correct
19 Correct 231 ms 16272 KB Output is correct
20 Correct 241 ms 12472 KB Output is correct
21 Correct 249 ms 19764 KB Output is correct
22 Correct 205 ms 19508 KB Output is correct
23 Correct 220 ms 18476 KB Output is correct
24 Correct 240 ms 18144 KB Output is correct
25 Correct 353 ms 17764 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6324 KB Output is correct
2 Correct 27 ms 6636 KB Output is correct
3 Incorrect 253 ms 18220 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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