CSES - KILO 2015 4/5

Submission details
Task:	Bus lines
Sender:	multiply and surrender
Submission time:	2015-09-30 18:44:38 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.11 s	details
#2	ACCEPTED	0.19 s	details
#3	ACCEPTED	0.09 s	details
#4	ACCEPTED	0.20 s	details
#5	ACCEPTED	0.16 s	details
#6	ACCEPTED	0.17 s	details
#7	ACCEPTED	0.21 s	details
#8	ACCEPTED	0.19 s	details
#9	ACCEPTED	0.08 s	details
#10	ACCEPTED	0.10 s	details
#11	ACCEPTED	0.09 s	details
#12	ACCEPTED	0.15 s	details
#13	ACCEPTED	0.23 s	details
#14	ACCEPTED	0.23 s	details
#15	ACCEPTED	0.23 s	details
#16	ACCEPTED	0.23 s	details
#17	ACCEPTED	0.23 s	details
#18	ACCEPTED	0.22 s	details
#19	ACCEPTED	0.23 s	details
#20	ACCEPTED	0.23 s	details
#21	ACCEPTED	0.22 s	details
#22	ACCEPTED	0.23 s	details
#23	ACCEPTED	0.23 s	details
#24	ACCEPTED	0.23 s	details
#25	ACCEPTED	0.23 s	details

Code

#include <iostream>
#include <map>


using namespace std;

int a[101010], b[101010];
int c[101010],d[101010];
int n,m,k;
map<int,int> v[101010];
int lab[101010];
int r;
int visit[101010];
int unio[101010];
int res[101010];

int dfs(int u) {
	if (visit[u]) return 0;
	lab[u]=r;
//	cout << u << ": " << lab[u] << "\n";
	visit[u]=1;
	for (auto x : v[u]) {
		if (x.second) dfs(x.first);
	}
	return 1;
}

int sama(int i,int j) {
	while(unio[i]!=i) i=unio[i];
	while(unio[j]!=j) j=unio[j];
	return i == j;
}

void yhd(int i, int j) {
	int ii=0;int jj=0;
	while(unio[i]!=i) {i=unio[i]; ii++;}
	while(unio[j]!=j) {j=unio[j]; jj++;}
	if (ii>jj) unio[j] = i;
	else unio[i]=j;
}

int main() {
	cin >> n >> m >> k;
	for (int i=0;i<m;i++) {
		cin >> a[i] >> b[i];
		if (v[a[i]].count(b[i])) {
		v[a[i]][b[i]]++;
		v[b[i]][a[i]]++;
		} else {
			v[a[i]][b[i]]=1;
			v[b[i]][a[i]]=1;
		}
	}
	for (int i=k-1;i>=0;i--) {
		int ind;
		cin >> ind;
		c[i] = a[--ind];
		d[i] = b[ind];
		v[c[i]][d[i]]--;
		v[d[i]][c[i]]--;
	}
//	for (int i=1;i<=n;i++) {
//		cout << i << ": ";
//		for (auto x : v[i]) cout << x << " ";
//		cout << "\n";
//	}
	r=0;
	for (int i=1;i<=n;i++) unio[i] = i;
	for (int i=1;i<=n;i++) {
		if (dfs(i)) r++;
	}
	for (int i=0;i<k;i++) {
		res[k-i-1] = r;
//		cout << c[i] << " " << d[i] << "\n";
//		cout << lab[c[i]] << " " << lab[d[i]] << "\n";
		if (!sama(lab[c[i]],lab[d[i]])) {
			yhd(lab[c[i]],lab[d[i]]);
			r--;
		}
	}
	for (int i=0;i<k;i++) cout << res[i] << " ";
	cout << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
`42712 59669 3327 27393 5935 40762 40800 33005 34639 19131 2850 ...` view save

correct output
`2937 2937 2937 2937 2937 2938 ...` view save

user output
`2937 2937 2937 2937 2937 2938 ...` view save

Test 2

Verdict: ACCEPTED

input
`76287 96164 41787 58072 25022 46787 62110 30339 48282 73612 52159 ...` view save

correct output
`6969 6969 6969 6969 6970 6970 ...` view save

user output
`6969 6969 6969 6969 6970 6970 ...` view save

Test 3

Verdict: ACCEPTED

input
`18336 40887 13506 13131 7525 2330 5108 1053 8852 2934 4194 ...` view save

correct output
`208 208 208 208 208 208 208 20...` view save

user output
`208 208 208 208 208 208 208 20...` view save

Test 4

Verdict: ACCEPTED

input
`10251 91042 26842 3863 3691 4990 6580 3722 1896 1240 6558 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 5

Verdict: ACCEPTED

input
`75339 65466 44858 37059 62665 14790 65885 12864 58973 70022 19675 ...` view save

correct output
`16333 16334 16335 16336 16336 ...` view save

user output
`16333 16334 16335 16336 16336 ...` view save

Test 6

Verdict: ACCEPTED

input
`2086 66519 52411 361 1822 723 1145 1914 914 2075 1759 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 7

Verdict: ACCEPTED

input
`38126 95132 68427 15424 17170 2781 12706 33834 13802 13405 25848 ...` view save

correct output
`246 246 246 246 246 246 246 24...` view save

user output
`246 246 246 246 246 246 246 24...` view save

Test 8

Verdict: ACCEPTED

input
`13057 86973 49052 5610 4743 1062 7853 6391 10993 5814 10957 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 9

Verdict: ACCEPTED

input
`88876 29498 13976 16610 72903 2735 47496 44512 709 3413 60896 ...` view save

correct output
`59380 59381 59382 59383 59384 ...` view save

user output
`59380 59381 59382 59383 59384 ...` view save

Test 10

Verdict: ACCEPTED

input
`54386 40792 30938 11372 35684 36569 35851 24804 11443 2433 7140 ...` view save

correct output
`15500 15501 15502 15502 15503 ...` view save

user output
`15500 15501 15502 15502 15503 ...` view save

Test 11

Verdict: ACCEPTED

input
`18637 33277 33188 6803 17956 14954 12901 7331 13934 15280 6584 ...` view save

correct output
`560 560 560 561 561 561 561 56...` view save

user output
`560 560 560 561 561 561 561 56...` view save

Test 12

Verdict: ACCEPTED

input
`2637 72943 18160 897 1538 720 703 1919 2314 1803 1644 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 13

Verdict: ACCEPTED

input
`100000 100000 100000 87033 99257 40607 9856 32664 94458 61822 19892 ...` view save

correct output
`16212 16212 16212 16213 16213 ...` view save

user output
`16212 16212 16212 16213 16213 ...` view save

Test 14

Verdict: ACCEPTED

input
`100000 100000 100000 4621 68476 54853 81760 28147 87423 33351 48197 ...` view save

correct output
`16294 16295 16295 16295 16296 ...` view save

user output
`16294 16295 16295 16295 16296 ...` view save

Test 15

Verdict: ACCEPTED

input
`100000 100000 100000 51596 84775 65582 47330 87748 35647 53679 16442 ...` view save

correct output
`16120 16121 16122 16122 16123 ...` view save

user output
`16120 16121 16122 16122 16123 ...` view save

Test 16

Verdict: ACCEPTED

input
`100000 100000 100000 69292 26196 54314 63616 95 16072 19077 67875 ...` view save

correct output
`16149 16149 16149 16149 16150 ...` view save

user output
`16149 16149 16149 16149 16150 ...` view save

Test 17

Verdict: ACCEPTED

input
`100000 100000 100000 97541 89807 88261 42118 68387 12007 50630 50 ...` view save

correct output
`16105 16105 16105 16105 16106 ...` view save

user output
`16105 16105 16105 16105 16106 ...` view save

Test 18

Verdict: ACCEPTED

input
`100000 100000 100000 91853 52153 10866 98151 37463 6198 60814 65027 ...` view save

correct output
`16154 16155 16155 16155 16156 ...` view save

user output
`16154 16155 16155 16155 16156 ...` view save

Test 19

Verdict: ACCEPTED

input
`100000 100000 100000 40682 32628 80240 43316 2162 93003 59820 88267 ...` view save

correct output
`16398 16398 16398 16398 16398 ...` view save

user output
`16398 16398 16398 16398 16398 ...` view save

Test 20

Verdict: ACCEPTED

input
`100000 100000 100000 55437 43499 70984 56856 86259 35090 95150 56215 ...` view save

correct output
`16044 16045 16045 16045 16046 ...` view save

user output
`16044 16045 16045 16045 16046 ...` view save

Test 21

Verdict: ACCEPTED

input
`100000 100000 100000 4134 98627 66480 41168 90133 75501 94062 11019 ...` view save

correct output
`16251 16252 16252 16252 16253 ...` view save

user output
`16251 16252 16252 16252 16253 ...` view save

Test 22

Verdict: ACCEPTED

input
`100000 100000 100000 6352 451 19430 47543 18870 69498 10423 18161 ...` view save

correct output
`16118 16118 16118 16119 16119 ...` view save

user output
`16118 16118 16118 16119 16119 ...` view save

Test 23

Verdict: ACCEPTED

input
`100000 100000 100000 47553 72232 19034 64055 24491 39922 98399 16192 ...` view save

correct output
`16199 16200 16201 16202 16202 ...` view save

user output
`16199 16200 16201 16202 16202 ...` view save

Test 24

Verdict: ACCEPTED

input
`100000 100000 100000 69140 89073 95544 9460 45106 70799 50772 94371 ...` view save

correct output
`16196 16196 16197 16198 16198 ...` view save

user output
`16196 16196 16197 16198 16198 ...` view save

Test 25

Verdict: ACCEPTED

input
`100000 100000 100000 22639 28340 10882 29245 74076 54240 87341 51204 ...` view save

correct output
`16129 16129 16129 16129 16129 ...` view save

user output
`16129 16129 16129 16129 16129 ...` view save

KILO 2015 4/5

Bus lines

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Tasks

Submissions (multiply and surrender)