제출 #533237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533237		rk42745417	철도 요금 (JOI16_ho_t3)	C++17	26 / 100	2574 ms	14484 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 1e5 + 25, M = 2e5 + 25;
vector<pair<int, int>> edge[N];
int add[M], ans[M], init_dis[N], dis[N];
int n;

void init_bfs() {
	memset(init_dis, 0x3f, sizeof init_dis);
	init_dis[1] = 0;
	queue<int> bfs;
	bfs.push(1);
	while(!bfs.empty()) {
		int u = bfs.front();
		bfs.pop();
		for(const auto &[v, _] : edge[u]) {
			if(init_dis[v] > init_dis[u] + 1) {
				init_dis[v] = init_dis[u] + 1;
				bfs.push(v);
			}
		}
	}
}

int solve(int t) {
	if(~ans[t])
		return ans[t];
	memset(dis, 0x3f, sizeof dis);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	dis[1] = 0;
	pq.push({0, 1});
	while(!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if(d > dis[u])
			continue;
		for(const auto &[v, c] : edge[u]) {
			int cost = 1 + (add[c] <= t);
			if(dis[v] > dis[u] + cost) {
				dis[v] = dis[u] + cost;
				pq.push({dis[v], v});
			}
		}
	}
	ans[t] = 0;
	for(int i = 1; i <= n; i++)
		ans[t] += dis[i] != init_dis[i];
	return ans[t];
}

signed main() {
	int m, q;
	cin >> n >> m >> q;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		edge[u].push_back({v, i});
		edge[v].push_back({u, i});
	}
	for(int i = 1, x; i <= q; i++) {
		cin >> x;
		add[x] = i;
	}
	for(int i = 1; i <= m; i++)
		if(add[i] == 0)
			add[i] = INF;

	init_bfs();

	memset(ans, -1, sizeof ans);
	for(int i = 1; i <= q; i++) {
		if(~ans[i])
			continue;
		solve(i);
		int l = i, r = q + 1;
		while(l < r) {
			int m = l + r >> 1;
			if(solve(m) > ans[i])
				r = m;
			else
				l = m + 1;
		}
		for(int j = i + 1; j < l; j++)
			ans[j] = ans[i];
	}
	for(int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

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

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |    int m = l + r >> 1;
      |            ~~^~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39