Submission #241753

#	Time	Username	Problem	Language	Result	Execution time	Memory
241753		dsjong	철도 요금 (JOI16_ho_t3)	C++14	100 / 100	580 ms	20324 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
bool vis[100005], good[200005],  queried[200005], leaf[100005], vis2[100005];
int dis[100005], root[100005], sz[100005];
pair<int, int>edges[200005];
vector<int>adj[100005], adj2[100005];
int find(int x){
	while(x!=root[x]){
		root[x]=root[root[x]];
		x=root[x];
	}
	return x;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, qq;
	cin>>n>>m>>qq;
	for(int i=1;i<=m;i++){
		int x, y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
		edges[i]={x, y};
	}
	queue<int>q;
	q.push(1);
	dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		vis[x]=true;
		q.pop();
		for(int y:adj[x]){
			if(vis[y]) continue;
			q.push(y);
			vis[y]=true;
			dis[y]=dis[x]+1;
		}
	}
	memset(good, 0, sizeof good);
	memset(queried, 0, sizeof queried);
	for(int i=1;i<=m;i++){
		if(abs(dis[edges[i].first]-dis[edges[i].second])==1){
			good[i]=true;
		}
	}
	vector<int>queries, ans;
	while(qq--){
		int x;
		cin>>x;
		queried[x]=true;
		queries.push_back(x);
	}
	for(int i=1;i<=m;i++){
		if(!queried[i] && good[i]){
			int x=edges[i].first, y=edges[i].second;
			if(dis[y]<dis[x]) swap(x, y);
			adj2[x].push_back(y);
		}
	}
	memset(vis, false, sizeof vis);
	int cnt=1;
	q.push(1);
	vis[1]=true;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:adj2[x]){
			if(vis[y]) continue;
			q.push(y);
			cnt++;
			vis[y]=true;
		}
	}
	ans.push_back(cnt);
	reverse(queries.begin(), queries.end());
	for(int i:queries){
		if(good[i]){
			int xi=edges[i].first, yi=edges[i].second;
			if(dis[yi]<dis[xi]) swap(xi, yi);
			//cout<<xi<<">>"<<yi<<endl;
			adj2[xi].push_back(yi);
			if(vis[yi] || !vis[xi]) goto hell;
			cnt++;
			q.push(yi);
			vis[yi]=true;
			while(!q.empty()){
				int x=q.front();
				q.pop();
				for(int y:adj2[x]){
					if(vis[y]) continue;
					q.push(y);
					vis[y]=true;
					cnt++;
				}
			}
		}
		hell:;
		//cout<<sz<<endl;
		ans.push_back(cnt);
	}
	ans.pop_back();
	reverse(ans.begin(), ans.end());
	for(int i:ans) cout<<n-i<<endl;
}

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