oj.uz

Submission #138189

# Submission time Handle Problem Language Result Execution time Memory
138189 2019-07-29T14:40:31 Z RockyB Highway Tolls (IOI18_highway) C++17
51 / 100
 450 ms 53196 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 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.s);
			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) {
				if (0) cerr << it.f << endl;
				X.pb(it);
			}

			int ind = id(X);
			// cerr <<
			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:226: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 5116 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5140 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5116 KB Output is correct
9 Correct 6 ms 5044 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 4984 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 8 ms 5112 KB Output is correct
2 Correct 30 ms 6352 KB Output is correct
3 Correct 261 ms 20584 KB Output is correct
4 Correct 255 ms 20612 KB Output is correct
5 Correct 251 ms 20016 KB Output is correct
6 Correct 242 ms 17736 KB Output is correct
7 Correct 251 ms 19224 KB Output is correct
8 Correct 263 ms 21436 KB Output is correct
9 Correct 233 ms 17468 KB Output is correct
10 Correct 245 ms 20372 KB Output is correct
11 Correct 254 ms 13616 KB Output is correct
12 Correct 265 ms 13556 KB Output is correct
13 Correct 253 ms 13560 KB Output is correct
14 Correct 261 ms 12880 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6008 KB Output is correct
2 Correct 47 ms 7032 KB Output is correct
3 Correct 67 ms 8128 KB Output is correct
4 Correct 183 ms 14292 KB Output is correct
5 Correct 185 ms 14384 KB Output is correct
6 Correct 192 ms 13960 KB Output is correct
7 Correct 171 ms 14328 KB Output is correct
8 Correct 191 ms 13968 KB Output is correct
9 Correct 187 ms 14288 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 20 ms 6496 KB Output is correct
3 Correct 165 ms 15656 KB Output is correct
4 Correct 239 ms 18452 KB Output is correct
5 Correct 253 ms 18712 KB Output is correct
6 Correct 263 ms 20316 KB Output is correct
7 Correct 236 ms 18992 KB Output is correct
8 Correct 247 ms 20520 KB Output is correct
9 Correct 243 ms 18576 KB Output is correct
10 Correct 255 ms 20552 KB Output is correct
11 Correct 254 ms 13660 KB Output is correct
12 Correct 274 ms 13428 KB Output is correct
13 Correct 277 ms 13084 KB Output is correct
14 Correct 282 ms 13132 KB Output is correct
15 Correct 222 ms 19080 KB Output is correct
16 Correct 233 ms 17844 KB Output is correct
17 Correct 275 ms 14056 KB Output is correct
18 Correct 269 ms 13460 KB Output is correct
19 Correct 237 ms 19084 KB Output is correct
20 Correct 268 ms 13304 KB Output is correct
21 Correct 450 ms 52552 KB Output is correct
22 Correct 432 ms 53196 KB Output is correct
23 Correct 305 ms 33628 KB Output is correct
24 Correct 327 ms 34164 KB Output is correct
25 Correct 428 ms 19464 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6440 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6900 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -