oj.uz

Submission #138195

# Submission time Handle Problem Language Result Execution time Memory
138195 2019-07-29T14:54:20 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 444 ms 53368 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 <int> V, U;
vector < pair <int, int > > g[MAX_N];

namespace Tree {
	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 id1(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 > dist * A) return id1(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id1(on);
	}

	int NeedLen;
	int id(vector < pair <int, vector <int> > > x) {
		if (sz(x) == 1) {
			if (0) cerr << " -> " << x[0].f << endl;
			vector <int> ind;
			for (auto it : g[x[0].f]) {
				// ind.pb(it);
				// cerr << min(dep[x[0].f], dep[it.f]) << ' ' << it.s << ' ' << NeedLen << endl;
				if (min(dep[x[0].f], dep[it.f]) == NeedLen) ind.pb(it.s);
			}
			// ioi
			return id1(ind);
		}
		int mid = sz(x) / 2;

		vector <int> q(m, 0);
		vector < pair <int, vector <int> > > sol;

		rep(i, 0, mid - 1) {
			for (auto it : g[x[i].f]) q[it.s] = 1;
			sol.pb(x[i]);
		}

		// if (0) cerr << sz(x) << endl;
		assert(sz(sol));

		ll cur = ask(q);
		// cerr << sz(sol) << ' ' << sol[0].f << ' ' << cur << endl;
		if (cur > (ll)dist * A) return id(sol);

		vector < pair <int, vector <int> > > on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id(on);
	}
	bool check(int x) {
		vector <int> q(m, 0);
		for (auto to : g[x]) q[to.s] = 1;
		return ask(q) == (ll)(dist - 1) * A + B; 
	}
	int GetS() {
		{ 
			vector <int> q(m, 0);
			dist = ask(q) / A;
		}
		// dist of path 
		bfs(0);
		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
		{
			map <int, vector <int > > edge_tov;
			for (auto i : edges[res]) {
				int x = V[i], y = U[i];
				if (dep[x] > dep[y]) swap(x, y);
				edge_tov[y].pb(i);
				// cerr << V[i] << ' ' << U[i] << " -> " << y << endl;
				if (dep[x] == dep[y]) edge_tov[x].pb(i);
			}
			vector < pair <int, vector <int > > > X;
			for (auto it : edge_tov) {
				X.pb(it);
			}
			NeedLen = res;
			int ind = id(X);
			// cerr <<
			// cerr << ind << endl;
			if (0) cerr << V[ind] << ' ' << U[ind] << endl;
			if (check(V[ind])) return V[ind];
			return U[ind];
		}
		// 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;
  V = _V;
  U = _U;
  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:233: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 5112 KB Output is correct
2 Correct 6 ms 5036 KB Output is correct
3 Correct 6 ms 5032 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 5032 KB Output is correct
6 Correct 6 ms 5032 KB Output is correct
7 Correct 8 ms 5032 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 6 ms 5004 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 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 29 ms 6320 KB Output is correct
3 Correct 254 ms 20552 KB Output is correct
4 Correct 258 ms 19660 KB Output is correct
5 Correct 252 ms 20040 KB Output is correct
6 Correct 291 ms 17328 KB Output is correct
7 Correct 222 ms 18864 KB Output is correct
8 Correct 233 ms 21396 KB Output is correct
9 Correct 237 ms 17444 KB Output is correct
10 Correct 252 ms 20328 KB Output is correct
11 Correct 298 ms 13624 KB Output is correct
12 Correct 278 ms 13556 KB Output is correct
13 Correct 278 ms 13292 KB Output is correct
14 Correct 262 ms 12896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6036 KB Output is correct
2 Correct 50 ms 7208 KB Output is correct
3 Correct 62 ms 8140 KB Output is correct
4 Correct 145 ms 14276 KB Output is correct
5 Correct 196 ms 14352 KB Output is correct
6 Correct 191 ms 13940 KB Output is correct
7 Correct 199 ms 14280 KB Output is correct
8 Correct 159 ms 13980 KB Output is correct
9 Correct 190 ms 14360 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5268 KB Output is correct
2 Correct 29 ms 6496 KB Output is correct
3 Correct 169 ms 15532 KB Output is correct
4 Correct 244 ms 18568 KB Output is correct
5 Correct 241 ms 18092 KB Output is correct
6 Correct 242 ms 20316 KB Output is correct
7 Correct 252 ms 18956 KB Output is correct
8 Correct 240 ms 20116 KB Output is correct
9 Correct 219 ms 18600 KB Output is correct
10 Correct 277 ms 20412 KB Output is correct
11 Correct 261 ms 13552 KB Output is correct
12 Correct 277 ms 12976 KB Output is correct
13 Correct 254 ms 13072 KB Output is correct
14 Correct 274 ms 13040 KB Output is correct
15 Correct 234 ms 19004 KB Output is correct
16 Correct 233 ms 17816 KB Output is correct
17 Correct 260 ms 14268 KB Output is correct
18 Correct 261 ms 13340 KB Output is correct
19 Correct 227 ms 19032 KB Output is correct
20 Correct 268 ms 13180 KB Output is correct
21 Correct 444 ms 52668 KB Output is correct
22 Correct 420 ms 53368 KB Output is correct
23 Correct 299 ms 33660 KB Output is correct
24 Correct 313 ms 33980 KB Output is correct
25 Correct 362 ms 19324 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6524 KB Output is correct
2 Correct 37 ms 7444 KB Output is correct
3 Incorrect 297 ms 24932 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 34 ms 6904 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -