oj.uz

Submission #138122

# Submission time Handle Problem Language Result Execution time Memory
138122 2019-07-29T11:41:07 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 255 ms 18532 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]);
		}

		// 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);
		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);
					edges[dep[x]].pb(to.s);
				}
			}
		}
		// ------------------------
		/*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]);
		}

		// 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();
		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;
		}
		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
		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
  Tree :: solve(FindS :: GetS());
  return;
  answer(0, N - 1);
}

Compilation message

highway.cpp: In function 'int FindS::GetS()':
highway.cpp:180: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 5040 KB Output is correct
2 Correct 6 ms 5032 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5036 KB Output is correct
5 Correct 6 ms 5036 KB Output is correct
6 Correct 7 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5028 KB Output is correct
9 Correct 6 ms 5028 KB Output is correct
10 Correct 6 ms 5028 KB Output is correct
11 Correct 6 ms 5032 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 7 ms 5088 KB Output is correct
2 Correct 35 ms 6044 KB Output is correct
3 Correct 177 ms 15796 KB Output is correct
4 Correct 212 ms 15360 KB Output is correct
5 Correct 201 ms 15804 KB Output is correct
6 Correct 205 ms 14964 KB Output is correct
7 Correct 207 ms 15820 KB Output is correct
8 Correct 196 ms 15232 KB Output is correct
9 Correct 191 ms 15828 KB Output is correct
10 Correct 206 ms 15376 KB Output is correct
11 Correct 228 ms 12004 KB Output is correct
12 Correct 219 ms 11872 KB Output is correct
13 Correct 205 ms 11676 KB Output is correct
14 Correct 223 ms 11504 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5900 KB Output is correct
2 Correct 34 ms 6836 KB Output is correct
3 Correct 52 ms 7784 KB Output is correct
4 Correct 170 ms 13332 KB Output is correct
5 Correct 149 ms 13280 KB Output is correct
6 Correct 184 ms 13284 KB Output is correct
7 Correct 192 ms 13268 KB Output is correct
8 Correct 161 ms 13280 KB Output is correct
9 Correct 163 ms 13240 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 46 ms 6100 KB Output is correct
3 Correct 152 ms 12772 KB Output is correct
4 Correct 230 ms 15044 KB Output is correct
5 Correct 235 ms 14836 KB Output is correct
6 Correct 191 ms 15708 KB Output is correct
7 Correct 195 ms 14944 KB Output is correct
8 Correct 197 ms 15324 KB Output is correct
9 Correct 215 ms 16172 KB Output is correct
10 Correct 228 ms 16168 KB Output is correct
11 Correct 229 ms 12256 KB Output is correct
12 Correct 222 ms 11860 KB Output is correct
13 Correct 231 ms 11388 KB Output is correct
14 Correct 219 ms 11592 KB Output is correct
15 Correct 202 ms 15236 KB Output is correct
16 Correct 207 ms 15300 KB Output is correct
17 Correct 225 ms 12148 KB Output is correct
18 Correct 224 ms 11964 KB Output is correct
19 Correct 196 ms 15208 KB Output is correct
20 Correct 188 ms 12116 KB Output is correct
21 Correct 193 ms 18532 KB Output is correct
22 Correct 177 ms 18528 KB Output is correct
23 Correct 209 ms 17528 KB Output is correct
24 Correct 203 ms 17328 KB Output is correct
25 Correct 255 ms 17224 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 11408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -