제출 #1256867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256867		altern23	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	484 ms	36736 KiB

2016_ho_t3

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

#define ll long long
#define fi first
#define sec second
#define pii pair<ll, ll>

const int MAXN = 1e5;
const ll INF = 1e18;

ll dist[MAXN + 5], ways[MAXN + 5];
vector<ll> adj[MAXN + 5], ctb[MAXN + 5];

map<pii, bool> vis;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll N, M, Q; cin >> N >> M >> Q;
	vector<pii> edges;
	for(int i = 1; i <= N; i++) dist[i] = INF;
	for(int i = 1; i <= M; i++){
		ll u, v; cin >> u >> v;
		edges.push_back({u, v});
		adj[u].push_back(v), adj[v].push_back(u);
	}
	
	queue<ll> q;
	dist[1] = 0, ways[1] = 1;
	q.push(1);
	
	for(;!q.empty();){
		auto idx = q.front(); q.pop();
		for(auto i : adj[idx]){
			if(dist[i] < dist[idx] + 1) continue;
			if(dist[i] == dist[idx] + 1){
				ways[i]++;
			}
			else{
				ways[i] = 1;
				dist[i] = dist[idx] + 1;
				q.push(i);
			}
		}
	}
	for(int i = 1; i <= N; i++){
		for(auto j : adj[i]){
			if(dist[i] + 1 == dist[j]){
				ctb[i].push_back(j);
			}
		}
	}
	
	set<ll> st;
	for(int i = 1; i <= Q; i++){
		ll idx; cin >> idx;
		--idx;
		if(vis.count({edges[idx].fi, edges[idx].sec}) || vis.count({edges[idx].sec, edges[idx].fi})){
			cout << (int)st.size() << "\n";
			continue;
		}
		queue<ll> q;
		if(dist[edges[idx].fi] == dist[edges[idx].sec] + 1){
			--ways[edges[idx].fi];
			if(!ways[edges[idx].fi]){
				if(st.find(edges[idx].fi) == st.end()){
					q.push(edges[idx].fi);
					for(;!q.empty();){
						auto idx = q.front(); q.pop();
						st.insert(idx);
						for(auto j : ctb[idx]){
							if(vis.count({idx, j}) || vis.count({j, idx})) continue;
							vis[{idx, j}] = 1;
							ways[j]--;
							if(!ways[j] && st.find(j) == st.end()){
								st.insert(j);
								q.push(j);
							}
						}
					}
				}
			}
		}
		if(dist[edges[idx].sec] == dist[edges[idx].fi] + 1){
			--ways[edges[idx].sec];
			if(!ways[edges[idx].sec]){
				if(st.find(edges[idx].sec) == st.end()){
					q.push(edges[idx].sec);
					for(;!q.empty();){
						auto idx = q.front(); q.pop();
						st.insert(idx);
						for(auto j : ctb[idx]){
							if(vis.count({idx, j}) || vis.count({j, idx})) continue;
							vis[{idx, j}] = 1;
							ways[j]--;
							if(!ways[j] && st.find(j) == st.end()){
								st.insert(j);
								q.push(j);
							}
						}
					}
				}
			}
		}
		cout << (int)st.size() << "\n";
		vis[{edges[idx].fi, edges[idx].sec}] = 1;
	}
}

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