Submission #138044

#	Time	Username	Problem	Language	Result	Execution time	Memory
138044		RockyB	Highway Tolls (IOI18_highway)	C++17	12 / 100	232 ms	12520 KiB

highway

// 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() {
		if (n != m + 1) return;

		{ 
			vector <int> q(m, 0);
			min_len = ask(q);
			depth = min_len / A;
		}
		dfs();
		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(0, i);
					else answer(0, it.f);
					return;
				}	
			}
		}
		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();
  return;
  answer(0, N - 1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31