답안 #818277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
818277 2023-08-10T04:15:28 Z pavement 통행료 (IOI18_highway) C++17
6 / 100
82 ms 12680 KB
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;

vector<int> distU, distV, prvU, prvV;
vector<vector<ii> > adj;
queue<int> Q;

void bfs(int s, vector<int> &dist, vector<int> &prv) {
	for (int i = 0; i < (int)dist.size(); i++) {
		dist[i] = (int)1e9;
	}
	dist[s] = 0;
	Q.push(s);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (auto [v, idx] : adj[u]) {
			if (dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				prv[v] = idx;
				Q.push(v);
			}
		}
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	distU.resize(N);
	distV.resize(N);
	prvU.resize(N);
	prvV.resize(N);
	adj.resize(N);
	int M = (int)U.size(), S, T;
	for (int i = 0; i < M; i++) {
		adj[U[i]].eb(V[i], i);
		adj[V[i]].eb(U[i], i);
	}
	ll original = ask(vector<int>(M, 0));
	int lo = 0, hi = M - 1, first_edge = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		vector<int> w(M, 0);
		for (int i = 0; i <= mid; i++) {
			w[i] = 1;
		}
		if (ask(w) != original) {
			first_edge = mid;
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
	assert(first_edge != -1);
	bfs(U[first_edge], distU, prvU);
	bfs(V[first_edge], distV, prvV);
	vector<int> sU, sV, treeU, treeV;
	for (int i = 0; i < N; i++) {
		if (i == U[first_edge] || i == V[first_edge]) continue;
		if (distU[i] < distV[i]) {
			sU.pb(i);
			int prv_node = U[prvU[i]] ^ V[prvU[i]] ^ i;
			if (distU[prv_node] < distV[prv_node]) {
				treeU.pb(prvU[i]);
			}
		} else {
			sV.pb(i);
			int prv_node = U[prvV[i]] ^ V[prvV[i]] ^ i;
			if (distU[prv_node] >= distV[prv_node]) {
				treeV.pb(prvV[i]);
			}
		}
	}
	
	sort(treeU.begin(), treeU.end());
	assert(unique(treeU.begin(), treeU.end()) == treeU.end());
	sort(treeV.begin(), treeV.end());
	assert(unique(treeV.begin(), treeV.end()) == treeV.end());
	
	vector<int> w(M, 1);
	for (int i : treeV) {
		w[i] = 0;
	}
	w[first_edge] = 0;
	ll tmp = ask(w);
	int U_len = (tmp - original) / (B - A);
	int V_len = original / A - U_len - 1;
	
	vector<int> o_w(M, 1);
	for (int i : treeU) {
		o_w[i] = 0;
	}
	for (int i : treeV) {
		o_w[i] = 0;
	}
	
	for (auto [dist, tree, prv, len, R] : {mt(distU, treeU, prvU, U_len, &S), mt(distV, treeV, prvV, V_len, &T)}) {
		vector<int> poss;
		for (int i : tree) {
			if (dist[U[i]] == len) {
				poss.pb(U[i]);
			}
			if (dist[V[i]] == len) {
				poss.pb(V[i]);
			}
		}
		assert(!poss.empty());
		sort(poss.begin(), poss.end());
		poss.erase(unique(poss.begin(), poss.end()), poss.end());
		while ((int)poss.size() > 1) {
			vector<int> w = o_w;
			for (int i = 0; i < (int)poss.size() / 2; i++) {
				w[prv[poss[i]]] = 1;
			}
			if (ask(w) > original) {
				int new_sz = (int)poss.size() / 2;
				while ((int)poss.size() != new_sz) poss.pop_back();
			} else {
				int new_sz = ((int)poss.size() + 1) / 2;
				reverse(poss.begin(), poss.end());
				while ((int)poss.size() != new_sz) poss.pop_back();
				reverse(poss.begin(), poss.end());
			}
		}
		*R = poss[0];
	}
	answer(S, T);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 648 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1640 KB Output is correct
2 Correct 13 ms 2968 KB Output is correct
3 Correct 31 ms 4288 KB Output is correct
4 Correct 54 ms 12296 KB Output is correct
5 Correct 71 ms 12348 KB Output is correct
6 Correct 53 ms 12680 KB Output is correct
7 Correct 82 ms 12456 KB Output is correct
8 Correct 56 ms 12280 KB Output is correct
9 Correct 56 ms 12544 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 392 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 1840 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 1708 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -