CSES - KILO 2016 5/5

Submission details
Task:	VERTEX COVER
Sender:	Team Olari
Submission time:	2016-10-04 19:04:29 +0300
Language:	C++
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.08 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.06 s	details
#4	ACCEPTED	0.07 s	details
#5	ACCEPTED	0.10 s	details
#6	ACCEPTED	0.11 s	details
#7	TIME LIMIT EXCEEDED	--	details
#8	TIME LIMIT EXCEEDED	--	details
#9	TIME LIMIT EXCEEDED	--	details
#10	ACCEPTED	0.13 s	details
#11	TIME LIMIT EXCEEDED	--	details
#12	TIME LIMIT EXCEEDED	--	details
#13	ACCEPTED	0.13 s	details
#14	ACCEPTED	0.08 s	details
#15	ACCEPTED	0.18 s	details
#16	ACCEPTED	0.22 s	details
#17	TIME LIMIT EXCEEDED	--	details
#18	ACCEPTED	0.11 s	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	ACCEPTED	0.17 s	details
#22	TIME LIMIT EXCEEDED	--	details
#23	ACCEPTED	0.18 s	details
#24	ACCEPTED	0.08 s	details
#25	ACCEPTED	0.15 s	details
#26	TIME LIMIT EXCEEDED	--	details
#27	TIME LIMIT EXCEEDED	--	details
#28	TIME LIMIT EXCEEDED	--	details
#29	TIME LIMIT EXCEEDED	--	details
#30	TIME LIMIT EXCEEDED	--	details

Code

#include <iostream>
#include <vector>
using namespace std;
#define N 101010
vector<int> v[N];
int t[2][N];
int z[N];
int u=0;
pair<int,int> a, b;
int x, y;
void h(int i, int p) {
	if (z[i]) {
		if(u==0){
			a= {i, p};
			++u;
		}else{
			b={i, p};
		}
		return;
	}
	z[i] = 1;
	for (int j : v[i]) {
		if (j == p) continue;
		h(j, i);
	}
}
void dp(int i, int p){
	t[1][i]=1;
	t[0][i]=0;
	if(i==x || i==y) t[0][i]=1e6;
	for(int j : v[i]){
		if(j == p || a==make_pair(i, j) || a == make_pair(j, i) || b == make_pair(i, j) || b == make_pair(j, i)) continue;
		dp(j, i);
		t[1][i] += min(t[0][j], t[1][j]);
		t[0][i] += t[1][j];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	
	for (int i = 0; i < n+1; ++i) {
		int a, b;
		cin >> a >> b;
		v[--a].push_back(--b);
		v[b].push_back(a);
	}
	
	int V=1e9;
	h(0, -1);
	x=a.first, y=b.first;
	dp(0, -1);
	V=min(V, t[0][0]);
	V=min(V, t[1][0]);
	x=a.first, y=b.second;
	dp(0, -1);
	V=min(V, t[0][0]);
	V=min(V, t[1][0]);
	x=a.second, y=b.first;
	dp(0, -1);
	V=min(V, t[0][0]);
	V=min(V, t[1][0]);
	x=a.second, y=b.second;
	dp(0, -1);
	V=min(V, t[0][0]);
	V=min(V, t[1][0]);
	cout << V << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`43516 31635 7283 407 22068 14527 27341 13988 3756 ...` view save

correct output
`15856` view save

user output
`15856` view save

Test 2

Verdict: ACCEPTED

input
`15844 11075 5963 12852 1355 12408 997 5774 1839 ...` view save

correct output
`6691` view save

user output
`6691` view save

Test 3

Verdict: ACCEPTED

input
`16739 5194 10683 1122 249 3384 12552 9483 5513 ...` view save

correct output
`6757` view save

user output
`6757` view save

Test 4

Verdict: ACCEPTED

input
`45585 2278 17306 29200 4367 3493 946 13733 29961 ...` view save

correct output
`16583` view save

user output
`16583` view save

Test 5

Verdict: ACCEPTED

input
`65713 48285 11821 34133 22499 14959 39378 27756 2333 ...` view save

correct output
`27673` view save

user output
`27673` view save

Test 6

Verdict: ACCEPTED

input
`65594 48205 44126 49025 17567 49495 29064 5497 9432 ...` view save

correct output
`26501` view save

user output
`26501` view save

Test 7

Verdict: TIME LIMIT EXCEEDED

input
`76352 41529 44956 24215 33162 32459 57488 36012 8978 ...` view save

correct output
`27769` view save

user output
(empty)

Test 8

Verdict: TIME LIMIT EXCEEDED

input
`19735 3280 11743 5800 4932 15996 16996 1326 8492 ...` view save

correct output
`8362` view save

user output
(empty)

Test 9

Verdict: TIME LIMIT EXCEEDED

input
`49843 38377 42277 22655 27295 9233 8151 20174 26700 ...` view save

correct output
`20103` view save

user output
(empty)

Test 10

Verdict: ACCEPTED

input
`93738 34468 1473 62502 21129 7249 69111 34431 14831 ...` view save

correct output
`34129` view save

user output
`34129` view save

Test 11

Verdict: TIME LIMIT EXCEEDED

input
`70512 59016 43446 23523 34215 40100 65349 32479 69170 ...` view save

correct output
`29712` view save

user output
(empty)

Test 12

Verdict: TIME LIMIT EXCEEDED

input
`77793 67362 43115 26066 53059 34877 28252 41322 27232 ...` view save

correct output
`31415` view save

user output
(empty)

Test 13

Verdict: ACCEPTED

input
`81528 17424 60496 16303 9750 72040 16424 73313 66255 ...` view save

correct output
`29740` view save

user output
`29740` view save

Test 14

Verdict: ACCEPTED

input
`87601 26609 79183 12401 22737 40749 41820 44416 43745 ...` view save

correct output
`36915` view save

user output
`36915` view save

Test 15

Verdict: ACCEPTED

input
`100000 99312 64091 74701 14263 18494 14204 48860 56668 ...` view save

correct output
`40376` view save

user output
`40376` view save

Test 16

Verdict: ACCEPTED

input
`100000 85199 85147 16157 86513 31941 9017 28468 14549 ...` view save

correct output
`50000` view save

user output
`50000` view save

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`100000 23889 65680 23889 43172 31662 23889 23889 14952 ...` view save

correct output
`3` view save

user output
(empty)

Test 18

Verdict: ACCEPTED

input
`100000 69560 99883 72675 99883 46326 77576 99883 92496 ...` view save

correct output
`6` view save

user output
`6` view save

Test 19

Verdict: TIME LIMIT EXCEEDED

input
`100000 28151 97740 74287 42190 55692 76617 51247 37435 ...` view save

correct output
`36374` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

input
`100000 92176 53508 59512 60686 3760 73799 25954 68463 ...` view save

correct output
`42107` view save

user output
(empty)

Test 21

Verdict: ACCEPTED

input
`100000 77208 54647 86577 72654 30560 44935 58433 65087 ...` view save

correct output
`40367` view save

user output
`40367` view save

Test 22

Verdict: TIME LIMIT EXCEEDED

input
`100000 11835 72732 46693 14441 91141 81072 9142 96454 ...` view save

correct output
`36396` view save

user output
(empty)

Test 23

Verdict: ACCEPTED

input
`100000 62977 19876 33643 71597 43079 56905 55474 63340 ...` view save

correct output
`42014` view save

user output
`42014` view save

Test 24

Verdict: ACCEPTED

input
`100000 10558 826 71579 31910 52499 85798 49687 29460 ...` view save

correct output
`40315` view save

user output
`40315` view save

Test 25

Verdict: ACCEPTED

input
`100000 42867 7204 6642 28627 52963 75885 5909 2124 ...` view save

correct output
`36378` view save

user output
`36378` view save

Test 26

Verdict: TIME LIMIT EXCEEDED

input
`100000 98353 70486 18269 81832 96346 42985 52089 65027 ...` view save

correct output
`42053` view save

user output
(empty)

Test 27

Verdict: TIME LIMIT EXCEEDED

input
`100000 95632 70669 80227 14695 8281 32693 36226 99062 ...` view save

correct output
`40405` view save

user output
(empty)

Test 28

Verdict: TIME LIMIT EXCEEDED

input
`100000 93396 66096 17209 78703 63472 8252 44686 81626 ...` view save

correct output
`36410` view save

user output
(empty)

Test 29

Verdict: TIME LIMIT EXCEEDED

input
`100000 76692 65797 61491 11409 1719 12971 71081 59660 ...` view save

correct output
`42226` view save

user output
(empty)

Test 30

Verdict: TIME LIMIT EXCEEDED

input
`100000 41478 47936 87485 27259 90595 12109 53850 41021 ...` view save

correct output
`40385` view save

user output
(empty)

KILO 2016 5/5

VERTEX COVER

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

Test 26

Test 27

Test 28

Test 29

Test 30

Tasks

Submissions (Team Olari)