oj.uz

Submission #138118

# Submission time Handle Problem Language Result Execution time Memory
138118 2019-07-29T11:33:56 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 265 ms 32936 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 7 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 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 7 ms 5032 KB Output is correct
8 Correct 6 ms 5020 KB Output is correct
9 Correct 6 ms 5028 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 5028 KB Output is correct
12 Correct 6 ms 4988 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5188 KB Output is correct
2 Correct 25 ms 5992 KB Output is correct
3 Correct 207 ms 15640 KB Output is correct
4 Correct 180 ms 15240 KB Output is correct
5 Correct 223 ms 15696 KB Output is correct
6 Correct 223 ms 14912 KB Output is correct
7 Correct 187 ms 15752 KB Output is correct
8 Correct 211 ms 15248 KB Output is correct
9 Correct 216 ms 15708 KB Output is correct
10 Correct 222 ms 15296 KB Output is correct
11 Correct 232 ms 13856 KB Output is correct
12 Correct 238 ms 14612 KB Output is correct
13 Correct 222 ms 13788 KB Output is correct
14 Correct 246 ms 13216 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6824 KB Output is correct
2 Correct 44 ms 8616 KB Output is correct
3 Correct 65 ms 10432 KB Output is correct
4 Correct 166 ms 21468 KB Output is correct
5 Correct 179 ms 21492 KB Output is correct
6 Correct 190 ms 21480 KB Output is correct
7 Correct 213 ms 21572 KB Output is correct
8 Correct 189 ms 21592 KB Output is correct
9 Correct 191 ms 21564 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 48 ms 6100 KB Output is correct
3 Correct 142 ms 12712 KB Output is correct
4 Correct 188 ms 14876 KB Output is correct
5 Correct 188 ms 14876 KB Output is correct
6 Correct 197 ms 15552 KB Output is correct
7 Correct 205 ms 14868 KB Output is correct
8 Correct 188 ms 15228 KB Output is correct
9 Correct 214 ms 15980 KB Output is correct
10 Correct 199 ms 16072 KB Output is correct
11 Correct 225 ms 13636 KB Output is correct
12 Correct 225 ms 14736 KB Output is correct
13 Correct 224 ms 13540 KB Output is correct
14 Correct 215 ms 14348 KB Output is correct
15 Correct 193 ms 15264 KB Output is correct
16 Correct 209 ms 15292 KB Output is correct
17 Correct 199 ms 14528 KB Output is correct
18 Correct 215 ms 14224 KB Output is correct
19 Correct 197 ms 15200 KB Output is correct
20 Correct 238 ms 15544 KB Output is correct
21 Correct 185 ms 18264 KB Output is correct
22 Correct 154 ms 18172 KB Output is correct
23 Correct 195 ms 17492 KB Output is correct
24 Correct 210 ms 18016 KB Output is correct
25 Correct 265 ms 24084 KB Output is correct

Subtask #5
0 / 18.0

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