Submission #921427

#	Time	Username	Problem	Language	Result	Execution time	Memory
921427		MilosMilutinovic	철도 요금 (JOI16_ho_t3)	C++14	100 / 100	151 ms	36712 KiB

2016_ho_t3

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q,tot,res;
int x[200005],y[200005],h[100005],nxt[400005],v[400005],d[100005],du[100005];
bool rem[100005],edg[400005];

void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}

void bfs(){
	for(int i=1;i<=n;i++) d[i]=-1;
	d[1]=0;
	queue<int> que;
	que.push(1);
	while(!que.empty()){
		int x=que.front();
		que.pop();
		for(int p=h[x];p;p=nxt[p]){
			if(d[v[p]]==-1){
				d[v[p]]=d[x]+1;
				que.push(v[p]);
			}
		}
	}
}

void work(int x){
	if(x==1||rem[x]) return;
	res++;
	rem[x]=true;
	for(int p=h[x];p;p=nxt[p]){
		if(d[v[p]]>d[x]&&!edg[p]){
			edg[p]=true;
			du[v[p]]--;
			if(du[v[p]]==0) work(v[p]);
		}
	}
}

int main(){
	n=readint();
	m=readint();
	q=readint();
	for(int i=1;i<=m;i++){
		x[i]=readint();
		y[i]=readint();
		addedge(x[i],y[i]);
	}
	bfs();
	map<pii,int> idx;
	for(int i=1;i<=n;i++){
		for(int p=h[i];p;p=nxt[p]){
			idx[mp(i,v[p])]=p;
		}
	}
	for(int i=1;i<=n;i++){
		for(int p=h[i];p;p=nxt[p]){
			if(d[v[p]]<d[i]) du[i]++;
		}
	}
	for(int i=2;i<=n;i++) if(du[i]==0) work(i);
	while(q--){
		int i=readint();
		if(d[x[i]]==d[y[i]]){
			printf("%d\n",res);
			continue;
		}
		if(d[x[i]]>d[y[i]]) swap(x[i],y[i]);
		if(rem[x[i]]){
			printf("%d\n",res);
			continue;
		}
		edg[idx[mp(x[i],y[i])]]=true;
		du[y[i]]--;
		if(du[y[i]]==0) work(y[i]);
		printf("%d\n",res);
	}
	return 0;
}

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