oj.uz

Submission #138120

# Submission time Handle Problem Language Result Execution time Memory
138120 2019-07-29T11:35:35 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 268 ms 33072 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;

	void dfs(int v = 0, int p = -1, int lvl = 0) {
		dep[v] = lvl;
		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;
		}
		dfs(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];
	void dfs(int v = 0, int p = -1, int lvl = 0) {
		dep[v] = lvl;
		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 
		dfs();
		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:139: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 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Correct 6 ms 5028 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5020 KB Output is correct
10 Correct 6 ms 4988 KB Output is correct
11 Correct 6 ms 5024 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5160 KB Output is correct
2 Correct 21 ms 6068 KB Output is correct
3 Correct 223 ms 15712 KB Output is correct
4 Correct 214 ms 15244 KB Output is correct
5 Correct 227 ms 15832 KB Output is correct
6 Correct 207 ms 14900 KB Output is correct
7 Correct 209 ms 15672 KB Output is correct
8 Correct 214 ms 15228 KB Output is correct
9 Correct 233 ms 15632 KB Output is correct
10 Correct 179 ms 15332 KB Output is correct
11 Correct 225 ms 13904 KB Output is correct
12 Correct 225 ms 14608 KB Output is correct
13 Correct 225 ms 13752 KB Output is correct
14 Correct 238 ms 13116 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6824 KB Output is correct
2 Correct 41 ms 8612 KB Output is correct
3 Correct 88 ms 10436 KB Output is correct
4 Correct 182 ms 21468 KB Output is correct
5 Correct 141 ms 21536 KB Output is correct
6 Correct 188 ms 21500 KB Output is correct
7 Correct 183 ms 21500 KB Output is correct
8 Correct 180 ms 21500 KB Output is correct
9 Correct 127 ms 21496 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5032 KB Output is correct
2 Correct 47 ms 6144 KB Output is correct
3 Correct 163 ms 12724 KB Output is correct
4 Correct 210 ms 14864 KB Output is correct
5 Correct 219 ms 14944 KB Output is correct
6 Correct 226 ms 15676 KB Output is correct
7 Correct 196 ms 14948 KB Output is correct
8 Correct 190 ms 15328 KB Output is correct
9 Correct 198 ms 15984 KB Output is correct
10 Correct 184 ms 16032 KB Output is correct
11 Correct 236 ms 13632 KB Output is correct
12 Correct 259 ms 14832 KB Output is correct
13 Correct 239 ms 13536 KB Output is correct
14 Correct 236 ms 14360 KB Output is correct
15 Correct 268 ms 15236 KB Output is correct
16 Correct 266 ms 15180 KB Output is correct
17 Correct 228 ms 14616 KB Output is correct
18 Correct 221 ms 14144 KB Output is correct
19 Correct 213 ms 15180 KB Output is correct
20 Correct 255 ms 15660 KB Output is correct
21 Correct 180 ms 18176 KB Output is correct
22 Correct 188 ms 18200 KB Output is correct
23 Correct 181 ms 17432 KB Output is correct
24 Correct 195 ms 18012 KB Output is correct
25 Correct 266 ms 24136 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 33072 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 60 ms 32260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -