제출 #122250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122250		Retro3014	철도 요금 (JOI16_ho_t3)	C++17	0 / 100	155 ms	15432 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> 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){
					pq.push({dist[gp[now][i].first], gp[now][i].first});
				}
				dist[gp[now][i].first] = dist[now]+1;
				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 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());
	init_g();
	for(int i=Q; i>=1; i--){
		while(!edge2.empty() && edge2.back().first>i){
			union_g(edge2.back().second.first, edge2.back().second.second);
			edge2.pop_back();
		}
		ans.pb(N - num[find_g(1)]);
	}
	while(!ans.empty()){
		printf("%d\n", ans.back());
		ans.pop_back();
	}
	return 0;
}

컴파일 시 표준 에러 (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 'int main()':
2016_ho_t3.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
2016_ho_t3.cpp:73: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:76: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:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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