제출 #297124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297124		RealSuperman1	통행료 (IOI18_highway)	C++14	90 / 100	376 ms	22844 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, gr;
vector < vector <int> > fixed_h;
vector <int> h;
vector <pii> par;
 
void dfs(int u, int p, int id_w, int height) {
	max_height = max(max_height, height);
	h[u] = height;
	par[u] = {p, id_w};
	for (auto to : gr[u])
		if (to.fi != p)
			dfs(to.fi, u, to.se, h[u] + 1);
}
 
int get_answer(vector <int> candidates, vector <int> vertical, ll val) {
	vector <int> L, R, w;
	while (candidates.size() > 1) {
		L.clear(); R.clear();
		w.assign(m, 0);
		for (int to : vertical)
			w[to] = 1;
		int lim = candidates.size() / 2;
		for (int i = 0; i < lim; i++) {
			int u = candidates[i];
			L.pb(u);
			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];
}
 
int solve_from(int C, int dist, ll val, vector <int> vertical) {
	max_height = 0; timer = 0;
	dfs(C, -1, -1, 0);
	fixed_h.resize(max_height + 1);
	for (int i = 0; i < n; i++)
		fixed_h[h[i]].pb(i);
	return get_answer(fixed_h[dist], vertical, val);
}

void bfs_tree(int x) {
	queue <int> q;
	q.push(x);
	vector <bool> vis(n, false);
	vis[x] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto to : g[cur]) {
			if (vis[to.fi])
				continue;
			vis[to.fi] = true;
			q.push(to.fi);
//			cout << cur << " " << to.fi << endl;
			gr[cur].pb(to);
			gr[to.fi].pb({cur, to.se});
		}
	}
}

bool cmp(pii x, pii y) {return x.se > y.se;}

void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
	n = n1;
	m = U.size();
	g.resize(n);
	gr.resize(n);
	for (int i = 0; i < m; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}
	vector <int> w(m, 0);
	ll val = ask(w);
	int dist = (val / (A * 1ll));
	int L = 0, R = n - 1, M, x = n;
	while (L <= R) {
		w.assign(m, 0);
		M = (L + R) / 2;
		for (int i = 0; i <= M; i++)
			for (auto to : g[i])
				w[to.se] = 1;
		ll curval = ask(w);
		if (curval > val) {
			x = min(x, M);
			R = M - 1;
		} else
			L = M + 1;
	}
//	cout << x << endl;
//	return;
	bfs_tree(x);
	vector <bool> vis(m, false);
	vector <int> vertical;
	for (int i = 0; i < n; i++)
		for (auto to : gr[i])
			vis[to.se] = true;
	for (int i = 0; i < m; i++)
		if (!vis[i])
			vertical.pb(i);
			
//	return;
	h.resize(n);
	par.resize(n);
	dfs(x, -1, -1, 0);
	vector <pii> c(n);
	for (int i = 0; i < n; i++)
		c[i] = {i, h[i]};
	sort(c.begin(), c.end(), cmp);
	L = 0; R = n - 1;
	int idc = n - 1;
	while (L <= R) {
		w.assign(m, 0);
		for (int to : vertical)
			w[to] = 1;
		M = (L + R) / 2;
		for (int i = 0; i <= M; i++)
			if (par[c[i].fi].fi != -1)
				w[par[c[i].fi].se] = 1;
		ll curval = ask(w);
		if (curval > val) {
			idc = min(idc, M);
			R = M - 1;
		} else
			L = M + 1;
	}
	int s = c[idc].fi;
//	cout << s << endl;
	int t = solve_from(s, dist, val, vertical);
//	cout << t << endl;
	answer(s, t);
}

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

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

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