Submission #1271425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271425		kaiboy	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	67 ms	11588 KiB

2016_ho_t3

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100000;
const int M = 200000;

int ij[M], tt[M], dd[N], tt_[N], qu[N], kk[M];
vector<int> eh[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m, q; cin >> n >> m >> q;
	for (int h = 0; h < m; h++) {
		int i, j; cin >> i >> j, i--, j--;
		ij[h] = i ^ j, tt[h] = q;
		eh[i].push_back(h);
		eh[j].push_back(h);
	}
	for (int t = 0; t < q; t++) {
		int h; cin >> h, h--;
		tt[h] = t;
	}
	for (int i = 0; i < n; i++)
		dd[i] = n;
	int cnt = 1; dd[0] = 0, tt_[0] = q;
	for (int head = 0; head < cnt; head++) {
		int i = qu[head], d = dd[i], t = tt_[i];
		if (t < q)
			kk[t]++;
		for (int h : eh[i]) {
			int j = i ^ ij[h];
			if (dd[j] == n)
				dd[qu[cnt++] = j] = d + 1;
			if (d < dd[j])
				tt_[j] = max(tt_[j], min(t, tt[h]));
		}
	}
	for (int k = 0, t = 0; t < q; t++)
		cout << (k += kk[t]) << '\n';
	return 0;
}

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