oj.uz

Submission #138130

# Submission time Handle Problem Language Result Execution time Memory
138130 2019-07-29T11:54:48 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 334 ms 18620 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);
		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:185: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 5080 KB Output is correct
2 Correct 6 ms 5032 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 5028 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 6 ms 5032 KB Output is correct
8 Correct 6 ms 5032 KB Output is correct
9 Correct 6 ms 5032 KB Output is correct
10 Correct 7 ms 4940 KB Output is correct
11 Correct 6 ms 4984 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 9 ms 5112 KB Output is correct
2 Correct 35 ms 6100 KB Output is correct
3 Correct 241 ms 16540 KB Output is correct
4 Correct 209 ms 16200 KB Output is correct
5 Correct 227 ms 16248 KB Output is correct
6 Correct 246 ms 15796 KB Output is correct
7 Correct 228 ms 16376 KB Output is correct
8 Correct 233 ms 16552 KB Output is correct
9 Correct 229 ms 16420 KB Output is correct
10 Correct 239 ms 16656 KB Output is correct
11 Correct 228 ms 12632 KB Output is correct
12 Correct 240 ms 12596 KB Output is correct
13 Correct 238 ms 12512 KB Output is correct
14 Correct 245 ms 12440 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5880 KB Output is correct
2 Correct 33 ms 6764 KB Output is correct
3 Correct 70 ms 7784 KB Output is correct
4 Correct 166 ms 13320 KB Output is correct
5 Correct 150 ms 13380 KB Output is correct
6 Correct 182 ms 13256 KB Output is correct
7 Correct 152 ms 13224 KB Output is correct
8 Correct 174 ms 13292 KB Output is correct
9 Correct 174 ms 13324 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 28 ms 6216 KB Output is correct
3 Correct 169 ms 13348 KB Output is correct
4 Correct 221 ms 16092 KB Output is correct
5 Correct 227 ms 15848 KB Output is correct
6 Correct 223 ms 16236 KB Output is correct
7 Correct 198 ms 16304 KB Output is correct
8 Correct 222 ms 16240 KB Output is correct
9 Correct 225 ms 16676 KB Output is correct
10 Correct 235 ms 16680 KB Output is correct
11 Correct 270 ms 12944 KB Output is correct
12 Correct 242 ms 12656 KB Output is correct
13 Correct 261 ms 11984 KB Output is correct
14 Correct 264 ms 12312 KB Output is correct
15 Correct 217 ms 16256 KB Output is correct
16 Correct 213 ms 15876 KB Output is correct
17 Correct 269 ms 12644 KB Output is correct
18 Correct 258 ms 12576 KB Output is correct
19 Correct 213 ms 16260 KB Output is correct
20 Correct 268 ms 12492 KB Output is correct
21 Correct 202 ms 18620 KB Output is correct
22 Correct 194 ms 18416 KB Output is correct
23 Correct 220 ms 17800 KB Output is correct
24 Correct 227 ms 17752 KB Output is correct
25 Correct 334 ms 17260 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6280 KB Output is correct
2 Correct 35 ms 6424 KB Output is correct
3 Incorrect 255 ms 17680 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 31 ms 6264 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -