제출 #1141787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141787		nuutsnoynton	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	74 ms	19004 KiB

2016_ho_t3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll M = 2e5 + 2;
const ll N = 1e5 + 2;
ll x[M], y[M], a[M];
int d[N], D[N];
vector < ll > adj[N];
ll used[M] = {0};
int main() {
 std::ios::sync_with_stdio(false);
 cin.tie(0);
 cout.tie(0);
	ll n, m, r, i, j,x1, y1, s, ans, t;

	cin >> n >> m >>t;
	for (i = 1; i <= n ; i ++) {
		D[i] = 1e9;
	}
	D[1] = 0;
	
	for (i = 1; i <= m; i ++) {
		cin >> x[i] >> y[i];
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	queue < ll > q;
	q.push(1);
	r = 0;	
	while(!q.empty()) {
		x1 = q.front();
		r ++;
		q.pop();
		for ( ll X : adj[x1]) {
			if ( D[X] != 1e9)  continue;
			D[X] = D[x1] + 1;
			q.push(X);
		}
	}
	for (i = 1; i <= n; i ++) {
		d[i] = D[i];
		D[i] = 1e9;
		adj[i].clear();
	}
	D[1] = 0;
	for (i = 1; i <= t; i ++) {
		cin >> a[i];
		used[a[i]] = 1;
	}
	
	for (i = 1; i <=m; i ++) {
		if ( used[i] == 0) {
			if ( d[x[i]] == d[y[i]] + 1) {
				adj[y[i]].push_back(x[i]);
			}
			if ( d[y[i]] == d[x[i]] + 1) {
				adj[x[i]].push_back(y[i]);
			}
		}
	}
	q.push(1);
	while(!q.empty()) {
		x1 = q.front();
		q.pop();
		for ( ll X : adj[x1]) {
			if ( D[X] != 1e9)  continue;
			D[X] = D[x1] + 1;
			q.push(X);
		}
	}
	s = 0;
	for (i = 1; i <= n; i ++) {
		if ( d[i] != 1e9 && d[i] == D[i]) s ++;
	}
	
	vector < ll > Ans;
	for (i = t; i >= 1; i --) {
		Ans.push_back(r - s);
		x1 = x[a[i]];
		y1 = y[a[i]];
		if ( d[x1] == d[y1] + 1) {
			adj[y1].push_back(x1);
			if ( d[y1] == D[y1] && d[x1] != D[x1] ) {
				s ++;
				D[x1] = d[x1];
				q.push(x1);
			}
		}
		if ( d[y1] == d[x1] + 1) {
			adj[x1].push_back(y1);
			if ( d[x1] == D[x1] && d[y1] != D[y1]) {
				s ++;
				D[y1] = d[y1];
				q.push(y1);
			}
		}
		while(!q.empty()) {
			x1 = q.front();
			q.pop();
			for ( ll X : adj[x1]) {
				if ( D[X] == d[X]) continue;
				D[X] = min(D[x1] + 1, D[X]);
				if ( D[X] == d[X]) {
					s ++;
					q.push(X);
				}
			}
		}
	
	}
	reverse(Ans.begin(), Ans.end());
	for (i = 0; i < Ans.size(); i ++) {
		cout << Ans[i] << "\n";
	}
}

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