Submission #122267

#	Time	Username	Problem	Language	Result	Execution time	Memory
122267		Retro3014	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	274 ms	23900 KiB

2016_ho_t3

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;

int N, M, Q;
vector<pair<pii, int> > edge;
vector<pii> gp[MAX_N+1];
int dist[MAX_N+1];
vector<pair<int, pii> > edge2;

priority_queue<pii, vector<pii>, greater<pii> > pq;

void dijk(){
	pq.push({0, 1});
	while(!pq.empty()){
		int now = pq.top().second; pq.pop();
		for(int i=0; i<gp[now].size(); i++){
			if(gp[now][i].first==1)	continue;
			if(dist[gp[now][i].first] == 0 || dist[gp[now][i].first]==dist[now]+1){
				if(dist[gp[now][i].first]==0){
					dist[gp[now][i].first] = dist[now]+1;
					pq.push({dist[gp[now][i].first], gp[now][i].first});
				}
				edge2.pb({gp[now][i].second, {now, gp[now][i].first}});
			}
		}
	}
}

int group[MAX_N+1], num[MAX_N+1];

void init_g(){
	for(int i=1; i<=N; i++){
		group[i] = i; num[i] = 1;
	}
}

int find_g(int x){
	return (x==group[x])? x : group[x] = find_g(group[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	if(x==y) return;
	group[x] = y;
	num[y]+=num[x];
}

vector<int> ans;

int cnt = 1;
vector<int> gp2[MAX_N+1];
bool chk[MAX_N+1];

void dfs(int x){
	if(chk[x])	return;
	chk[x] = true; cnt++;
	for(int i=0; i<gp2[x].size(); i++){
		dfs(gp2[x][i]);
	}
}

void add(int x, int y){
	gp2[x].pb(y);
	//cout<<x<<" "<<y<<endl;
	//cout<<chk[x]<<" "<<chk[y]<<endl;
	if(chk[x]){
		if(chk[y])	return;
		dfs(y);
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<=M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		edge.pb({{a, b}, Q+1});
	}
	for(int i=1; i<=Q; i++){
		int x;
		scanf("%d", &x);
		edge[x-1].second = i;
	}
	for(int i=0; i<edge.size(); i++){
		gp[edge[i].first.first].pb({edge[i].first.second, edge[i].second});
		gp[edge[i].first.second].pb({edge[i].first.first, edge[i].second});	
	}
	dijk();
	sort(edge2.begin(), edge2.end());
	/*for(int i=0; i<edge2.size(); i++){
		printf("%d %d\n", edge2[i].second.first, edge2[i].second.second);
	}*/ 
	//init_g();
	chk[1] = true;
	for(int i=Q; i>=1; i--){
		//cout<<i<<endl;
		while(!edge2.empty() && edge2.back().first>i){
			add(edge2.back().second.first, edge2.back().second.second);
			edge2.pop_back();
		}
		ans.pb(N-cnt);
	}
	while(!ans.empty()){
		printf("%d\n", ans.back());
		ans.pop_back();
	}
	return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'void dijk()':
2016_ho_t3.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<gp[now].size(); i++){
                ~^~~~~~~~~~~~~~~
2016_ho_t3.cpp: In function 'void dfs(int)':
2016_ho_t3.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp2[x].size(); i++){
               ~^~~~~~~~~~~~~~
2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
2016_ho_t3.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t3.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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