Submission #52142

#	Time	Username	Problem	Language	Result	Execution time	Memory
52142		ainta	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	366 ms	122468 KiB

2016_ho_t3

#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
using namespace std;
int SZ[N_], UF[N_];
vector<int>T[N_];
vector<int>E[N_], G[N_];
struct Edge {
	int a, b, t;
}w[N_];
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
int n, m, QQ, Q[N_], head, tail, v[N_], D[N_], P[N_];
void BFS(int st) {
	head = tail = 0;
	int i;
	for (i = 1; i <= n; i++)D[i] = 1e9;
	Q[++tail] = st, D[st] = 0, v[st] = 1;
	while (head < tail) {
		int x = Q[++head];
		for (auto &t : E[x]) {
			if (!v[t]) {
				v[t] = 1;
				D[t] = D[x] + 1;
				Q[++tail] = t;
			}
		}
	}
}
int res;
void Put(int a, int b) {
	if (D[a] > D[b])swap(a, b);
	if (D[a] == D[b])return;
	G[a].push_back(b);
	if(!P[a] || P[b])return;
	head = tail = 0;
	Q[++tail] = b;
	P[b] = 1; res--;
	while (head < tail) {
		int x = Q[++head];
		for (auto &t : G[x]) {
			if (!P[t]) {
				P[t] = 1;
				Q[++tail] = t;
				res--;
			}
		}
	}
}
int Res[N_];
int main() {
	int i, a, b;
	scanf("%d%d%d", &n, &m, &QQ);
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
		E[w[i].a].push_back(w[i].b);
		E[w[i].b].push_back(w[i].a);
	}
	for (i = 1; i <= QQ; i++) {
		scanf("%d", &a);
		w[a].t = 1;
		T[i - 1].push_back(a);
	}
	for (i = 1; i <= m; i++) {
		if (!w[i].t)T[QQ].push_back(i);
	}
	BFS(1);
	P[1] = 1;
	res = n-1;
	for (i = QQ; i >= 1; i--) {
		for (auto &x : T[i]) {
			Put(w[x].a, w[x].b);
		}
		Res[i] = res;
	}
	for (i = 1; i <= QQ; i++)printf("%d\n", Res[i]);
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:55:12: warning: unused variable 'b' [-Wunused-variable]
  int i, a, b;
            ^
2016_ho_t3.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &QQ);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

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