oj.uz

Submission #52142

# Submission time Handle Problem Language Result Execution time Memory
52142 2018-06-24T07:25:37 Z ainta None (JOI16_ho_t3) C++17
100 / 100
 366 ms 122468 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 15 ms 14756 KB Output is correct
4 Correct 15 ms 14856 KB Output is correct
5 Correct 16 ms 14856 KB Output is correct
6 Correct 14 ms 14856 KB Output is correct
7 Correct 14 ms 14892 KB Output is correct
8 Correct 14 ms 14892 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 15 ms 14756 KB Output is correct
4 Correct 15 ms 14856 KB Output is correct
5 Correct 16 ms 14856 KB Output is correct
6 Correct 14 ms 14856 KB Output is correct
7 Correct 14 ms 14892 KB Output is correct
8 Correct 14 ms 14892 KB Output is correct
9 Correct 237 ms 27704 KB Output is correct
10 Correct 185 ms 30096 KB Output is correct
11 Correct 176 ms 32444 KB Output is correct
12 Correct 185 ms 34892 KB Output is correct
13 Correct 192 ms 37212 KB Output is correct
14 Correct 212 ms 39908 KB Output is correct
15 Correct 134 ms 39908 KB Output is correct
16 Correct 136 ms 40580 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 44052 KB Output is correct
2 Correct 209 ms 46552 KB Output is correct
3 Correct 140 ms 47164 KB Output is correct
4 Correct 203 ms 50564 KB Output is correct
5 Correct 200 ms 53148 KB Output is correct
6 Correct 194 ms 55444 KB Output is correct
7 Correct 123 ms 55444 KB Output is correct
8 Correct 113 ms 56068 KB Output is correct
9 Correct 78 ms 56068 KB Output is correct
10 Correct 73 ms 56068 KB Output is correct
11 Correct 232 ms 63996 KB Output is correct
12 Correct 262 ms 65232 KB Output is correct
13 Correct 243 ms 67504 KB Output is correct
14 Correct 222 ms 70940 KB Output is correct
15 Correct 267 ms 74240 KB Output is correct
16 Correct 237 ms 76176 KB Output is correct
17 Correct 237 ms 81488 KB Output is correct
18 Correct 186 ms 81488 KB Output is correct
19 Correct 300 ms 89440 KB Output is correct
20 Correct 244 ms 89524 KB Output is correct
21 Correct 170 ms 89524 KB Output is correct
22 Correct 151 ms 89524 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 15 ms 14756 KB Output is correct
4 Correct 15 ms 14856 KB Output is correct
5 Correct 16 ms 14856 KB Output is correct
6 Correct 14 ms 14856 KB Output is correct
7 Correct 14 ms 14892 KB Output is correct
8 Correct 14 ms 14892 KB Output is correct
9 Correct 237 ms 27704 KB Output is correct
10 Correct 185 ms 30096 KB Output is correct
11 Correct 176 ms 32444 KB Output is correct
12 Correct 185 ms 34892 KB Output is correct
13 Correct 192 ms 37212 KB Output is correct
14 Correct 212 ms 39908 KB Output is correct
15 Correct 134 ms 39908 KB Output is correct
16 Correct 136 ms 40580 KB Output is correct
17 Correct 217 ms 44052 KB Output is correct
18 Correct 209 ms 46552 KB Output is correct
19 Correct 140 ms 47164 KB Output is correct
20 Correct 203 ms 50564 KB Output is correct
21 Correct 200 ms 53148 KB Output is correct
22 Correct 194 ms 55444 KB Output is correct
23 Correct 123 ms 55444 KB Output is correct
24 Correct 113 ms 56068 KB Output is correct
25 Correct 78 ms 56068 KB Output is correct
26 Correct 73 ms 56068 KB Output is correct
27 Correct 232 ms 63996 KB Output is correct
28 Correct 262 ms 65232 KB Output is correct
29 Correct 243 ms 67504 KB Output is correct
30 Correct 222 ms 70940 KB Output is correct
31 Correct 267 ms 74240 KB Output is correct
32 Correct 237 ms 76176 KB Output is correct
33 Correct 237 ms 81488 KB Output is correct
34 Correct 186 ms 81488 KB Output is correct
35 Correct 300 ms 89440 KB Output is correct
36 Correct 244 ms 89524 KB Output is correct
37 Correct 170 ms 89524 KB Output is correct
38 Correct 151 ms 89524 KB Output is correct
39 Correct 314 ms 98192 KB Output is correct
40 Correct 321 ms 101736 KB Output is correct
41 Correct 206 ms 101736 KB Output is correct
42 Correct 310 ms 107760 KB Output is correct
43 Correct 366 ms 111372 KB Output is correct
44 Correct 283 ms 115200 KB Output is correct
45 Correct 271 ms 118652 KB Output is correct
46 Correct 202 ms 118652 KB Output is correct
47 Correct 141 ms 118652 KB Output is correct
48 Correct 147 ms 118652 KB Output is correct
49 Correct 122 ms 118652 KB Output is correct
50 Correct 139 ms 118652 KB Output is correct
51 Correct 109 ms 119556 KB Output is correct
52 Correct 102 ms 120768 KB Output is correct
53 Correct 101 ms 121308 KB Output is correct
54 Correct 94 ms 122468 KB Output is correct