제출 #294883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294883		RealSuperman1	통행료 (IOI18_highway)	C++14	18 / 100	3065 ms	262148 KiB

highway

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>

using namespace std;

//const int N = 2e5 + 10;

int n, m, max_height = 0, timer;
vector < vector <pii> > g;
vector < vector <int> > fixed_h;
vector <int> h, tin, tout;
vector <pii> par;

void dfs(int u, int p, int id_w, int height) {
	tin[u] = ++timer;
	max_height = max(max_height, height);
	h[u] = height;
	par[u] = {p, id_w};
	for (auto to : g[u])
		if (to.fi != p)
			dfs(to.fi, u, to.se, h[u] + 1);
	tout[u] = ++timer;
}

bool parent(int par, int u) {
	return (tin[par] <= tin[u] && tout[par] >= tout[u]);
}

ll find_val() {
	vector <int> w(m, 0);
	return ask(w);
}

int find_height_lca(ll val) {
	int L = 0, R = max_height, M, ans = 0;
	vector <int> w;
	while (L <= R) {
		M = (L + R) / 2;
		w.assign(m, 0);
		for (int height = 0; height <= M; height++)
			for (int to : fixed_h[height]) {
				if (par[to].se >= 0)
					w[par[to].se] = 1;
			}
		ll curval = ask(w);
		if (curval > val) {
			R = M - 1;
		} else {
			ans = max(ans, M);
			L = M + 1;
		}
	}
	return ans;
}

int get_answer(vector <int> candidates, ll val, bool flag=false) {
	vector <int> L, R, w;
	while (candidates.size() > 1) {
		L.clear(); R.clear();
		w.assign(m, 0);
		int lim = candidates.size() / 2;
		for (int i = 0; i < lim; i++) {
			int u = candidates[i];
			L.pb(u);
			if (!flag) {
				for (auto to : g[u])
					if (par[u].fi != to.fi)
						w[to.se] = 1;
			} else {
				if (par[u].se >= 0)
					w[par[u].se] = 1;
			}
		}
		for (int i = lim; i < candidates.size(); i++) {
			R.pb(candidates[i]);
		}
		ll curval = ask(w);
		if (curval > val)
			candidates = L;
		else
			candidates = R;
	}
	return candidates[0];
}

vector <int> get_candidates(int u, int height) {
	vector <int> ans = {};
	for (int to : fixed_h[height])
		if (parent(u, to))
			ans.pb(to);
	return ans;
}

int find_lca(int height, ll val) {
	return get_answer(get_candidates(0, height), val);
}

int find_first_end(int lca, int dist, ll val) {
	int L = h[lca] + (dist + 1) / 2, R = min(max_height, h[lca] + dist), M, ch = h[lca];
	vector < vector <int> > fixed_h_cur;
	fixed_h_cur.resize(max_height + 1);
	for (int i = 0; i <= max_height; i++)
		for (int to : fixed_h[i])
			if (parent(lca, to))
				fixed_h_cur[i].pb(to); 
	vector <int> w;
	while (L <= R) {
		M = (L + R) / 2;
		w.assign(m, 0);
		for (int height = M; height <= R; height++) {
			for (int to : fixed_h_cur[height]) {
				if (par[to].se >= 0)
					w[par[to].se] = 1;
			}
		}
		ll curval = ask(w);
		if (curval > val) {
			ch = max(ch, M);
			L = M + 1;
		} else
			R = M - 1;
	}
	return get_answer(get_candidates(lca, ch), val, true);
}

void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
	n = n1;
	m = U.size();
	g.resize(n);
	h.resize(n);
	par.resize(n);
	tin.resize(n);
	tout.resize(n);
	for (int i = 0; i < m; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}
	timer = 0;
	dfs(0, -1, -1, 0);
	fixed_h.resize(max_height + 1);
	for (int i = 0; i < n; i++)
		fixed_h[h[i]].pb(i);
	ll val = find_val();
	int dist = val / (A * 1ll);
	int height_lca = find_height_lca(val);
	
	int lca = find_lca(height_lca, val);
	int C = find_first_end(lca, dist, val);
	int remain_dist = dist - (h[C] - h[lca]);
	if (remain_dist == 0) {
		answer(C, lca);
		return;
	}
	vector <int> candidates = {};
	for (auto cur : g[lca]) {
		int to = cur.fi;
		if (par[lca].fi == to || (parent(to, C)))
			continue;
		vector <int> tmp = get_candidates(to, h[lca] + remain_dist);
		for (int x : tmp)
			candidates.pb(x);
	}
	int T = get_answer(candidates, val, true);
	answer(C, T);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'int get_answer(std::vector<int>, long long int, bool)':
highway.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = lim; i < candidates.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

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