CSES - KILO 2015 2/5

Submission details
Task:	Hacker
Sender:	multiply and surrender
Submission time:	2015-09-16 19:45:56 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.06 s	details
#4	ACCEPTED	0.06 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.05 s	details
#8	ACCEPTED	0.06 s	details
#9	ACCEPTED	0.06 s	details
#10	ACCEPTED	0.06 s	details
#11	ACCEPTED	0.30 s	details
#12	ACCEPTED	0.30 s	details
#13	ACCEPTED	0.30 s	details
#14	ACCEPTED	0.30 s	details
#15	ACCEPTED	0.29 s	details
#16	ACCEPTED	0.30 s	details
#17	ACCEPTED	0.30 s	details
#18	ACCEPTED	0.30 s	details
#19	ACCEPTED	0.30 s	details
#20	ACCEPTED	0.31 s	details
#21	ACCEPTED	0.29 s	details
#22	ACCEPTED	0.38 s	details
#23	ACCEPTED	0.29 s	details
#24	ACCEPTED	0.29 s	details
#25	ACCEPTED	0.39 s	details
#26	ACCEPTED	0.28 s	details
#27	ACCEPTED	0.28 s	details
#28	ACCEPTED	0.33 s	details
#29	ACCEPTED	0.29 s	details
#30	ACCEPTED	0.29 s	details
#31	ACCEPTED	0.33 s	details
#32	ACCEPTED	0.29 s	details
#33	ACCEPTED	0.30 s	details
#34	ACCEPTED	0.28 s	details
#35	ACCEPTED	0.29 s	details
#36	ACCEPTED	0.28 s	details

Compiler report

input/code.cpp: In function 'int dfs(int, int, int)':
input/code.cpp:112:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j=0;j<v[i].size();j++) {
                ^
input/code.cpp: In function 'int main()':
input/code.cpp:162:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0;j<v[p4].size();j++) {
                  ^
input/code.cpp:183:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0;j<v[tmp].size();j++) {
                  ^

Code

#include <iostream>
#include <vector>
#include <deque>

#define mp make_pair
#define F first
#define S second
#define N (1<<19)

using namespace std;

pair<int,int> sPuu[2*N];
int ind;
int k[201010];
vector<int> v[201010];
int n,m;
int u,w,d;
int visit[201010];
int dep[201010];
int asd[201010];

int par[201010][18];
int chk[201010];
int q1,p1, q2,p2;
deque<int> dq;
deque<int> dq2;

int rise(int i, int k) {
	int res = i;
	int hlp = 0;
	while (k>0) {
		if(k%2 == 1) {
			res = par[res][hlp];
		}
		hlp++;
		k/=2;
	}
//	cout << "RISEN\n";
	return res;
}

void makeTree() {
	for (int j=N-1;j>0;j--) {
		if (sPuu[2*j].S > sPuu[2*j+1].S) sPuu[j] = sPuu[2*j+1];
		else sPuu[j] = sPuu[2*j];
	}
//	cout << "TREE MADE\n";
}

int askDist(int i,int j) {
	int i1 = k[i]; int j1 = k[j];
	int parsa = 101010101;
	if (i1>j1) swap(i1,j1);
	while (i1<=j1) {
		if (i1%2 == 1) {
			if (sPuu[i1].S < parsa) {
				parsa = sPuu[i1].S;
				
			}
			i1++;
		}
		if (j1%2 == 0) {
			if (parsa > sPuu[j1].S) {
				parsa = sPuu[j1].S;
				
			}
			j1--;
		}
		i1/=2; j1/=2;
//		cout << i1 << " " << j1 << "\n";
	}
//	cout << "DIST ASKED\n";
	return sPuu[k[i]].S + sPuu[k[j]].S -2*parsa;
}

int askPar(int i,int j) {
	i=k[i];j=k[j];
	if (i>j) swap(i,j);
	int parsa = 1010101010;
	int parind = -1;
	while (i<=j) {
		if (i%2 == 1) {
			if (sPuu[i].S < parsa) {
				parsa = sPuu[i].S;
				parind = sPuu[i].F;
			}
			i++;
		}
		if (j%2 == 0) {
			if (sPuu[j].S < parsa) {
				parsa = sPuu[j].S;
				parind = sPuu[j].F;
			}
			j--;
		}
		i/=2;
		j/=2;
	}
//	cout << "PARENT ASKED\n";
	return parind;
}

int dfs(int i,int dist, int l) {
	if (visit[i]) return 0;
	par[i][0] = l;
	for (int j=1;j<18;j++) par[i][j] = par[par[i][j-1]][j-1];
	k[i] = N+ind;
//	cout << i << ": " << k[i] << "\n";
	sPuu[N+ind] = mp(i,dist);
	ind++;
	visit[i] = 1;
	for (int j=0;j<v[i].size();j++) {
		if (dfs(v[i][j],dist+1,i)) {
			sPuu[N+ind] = mp(i,dist);
			ind++;
		}
	}
	return 1;
}

int main() {
	cin >> n >> m;
	for (int i=1;i<n;i++) {
		cin >> u >> w;
		v[u].push_back(w);
		v[w].push_back(u);
	}
	dfs(1,1,0);
//	cout << "DFS READY\n";

	makeTree();
	cin >> p1 >> q1;
	chk[p1] = 1;
	for (int i=1;i<m;i++) {
		cin >> p2 >> q2;
		if (chk[p2]) continue;
//		cout << "ASKING DIST\n";
		int distance = askDist(p1,p2);
		int tmp = askPar(p1,p2);
		if (distance == q1+q2) {
			cout << "1 ";
			if (askDist(tmp,p1) > q1) {
				cout << rise(p1,q1) << "\n";
			} else {
				cout << rise(p2,q2) << "\n";
			}
			return 0;
		}
		int p3;
		int q3 = (q1+q2-distance)/2;
		if (askDist(tmp, p1) > q1 - q3) {
			p3 = rise(p1,q1-q3);
		} else {
			p3 = rise(p2,q2-q3);
		}
		if (p1 != p3) dq.push_back(p1);
		if (p2 != p3) dq.push_back(p2);
		while(!dq.empty()) {
			int p4 = dq.back();
			dq.pop_back();
			chk[p4] = 1;
			for (int j=0;j<v[p4].size();j++) {
				if (v[p4][j] != p3 && !chk[v[p4][j]]) dq.push_back(v[p4][j]);
			}
		}
		p1 = p3;
		q1 = q3;
	}

	dq.push_back(p1);
	dq2.push_back(0);
	asd[p1] = 1;
	int val = 0;
	int parsa = -1;
	while (!dq.empty()) {
		int tmp = dq.back();
		dq.pop_back();
		asd[tmp] = 1;
		int fasd = dq2.back();
		dq2.pop_back();
		if (fasd == q1) {val++;if (parsa == -1) parsa = tmp;}
		else {
			for (int j=0;j<v[tmp].size();j++) {
				if (!asd[v[tmp][j]] && !chk[v[tmp][j]]) {
					dq.push_back(v[tmp][j]);
					dq2.push_back(fasd+1);
				}
			}
		}
	}
	cout << val << " " << parsa << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
`5 3 2 1 1 4 2 3 4 5 ...` view save

correct output
`1 3` view save

user output
`1 3` view save

Test 2

Verdict: ACCEPTED

input
`2 1 2 1 1 1` view save

correct output
`1 2` view save

user output
`1 2` view save

Test 3

Verdict: ACCEPTED

input
`4 2 1 3 3 4 2 1 3 1 ...` view save

correct output
`1 4` view save

user output
`1 4` view save

Test 4

Verdict: ACCEPTED

input
`8 4 3 8 3 7 3 2 5 8 ...` view save

correct output
`1 4` view save

user output
`1 4` view save

Test 5

Verdict: ACCEPTED

input
`8 2 1 5 2 1 5 4 7 5 ...` view save

correct output
`1 1` view save

user output
`1 1` view save

Test 6

Verdict: ACCEPTED

input
`88 58 16 63 16 55 45 16 16 76 ...` view save

correct output
`1 16` view save

user output
`1 16` view save

Test 7

Verdict: ACCEPTED

input
`90 34 3 30 33 3 3 1 3 16 ...` view save

correct output
`1 73` view save

user output
`1 73` view save

Test 8

Verdict: ACCEPTED

input
`68 64 65 37 26 37 37 2 37 16 ...` view save

correct output
`1 14` view save

user output
`1 14` view save

Test 9

Verdict: ACCEPTED

input
`98 90 82 89 89 72 89 24 89 66 ...` view save

correct output
`1 38` view save

user output
`1 38` view save

Test 10

Verdict: ACCEPTED

input
`45 43 16 24 11 24 24 14 39 16 ...` view save

correct output
`1 11` view save

user output
`1 11` view save

Test 11

Verdict: ACCEPTED

input
`200000 10000 108969 124359 95689 6026 116305 139666 24031 23504 ...` view save

correct output
`2269 100022 100029 100048 100187 10...` view save

user output
`2269 101746` view save

Test 12

Verdict: ACCEPTED

input
`200000 30000 149634 101097 7189 8578 110942 104503 110094 199531 ...` view save

correct output
`12594 100006 100022 100025 100028 10...` view save

user output
`12594 150940` view save

Test 13

Verdict: ACCEPTED

input
`200000 10001 9664 10422 101570 162282 21567 87519 75017 10098 ...` view save

correct output
`4469 100033 100068 100071 100074 10...` view save

user output
`4469 121647` view save

Test 14

Verdict: ACCEPTED

input
`200000 30001 192593 161643 133646 146752 70341 87021 85165 3436 ...` view save

correct output
`646 100376 100431 100629 100865 10...` view save

user output
`646 193832` view save

Test 15

Verdict: ACCEPTED

input
`200000 10003 182120 107802 111504 176786 116392 192800 39491 8466 ...` view save

correct output
`1 187998` view save

user output
`1 187998` view save

Test 16

Verdict: ACCEPTED

input
`200000 30003 100234 176124 72445 20075 27078 77532 6054 17091 ...` view save

correct output
`1013 100101 100226 100318 100331 10...` view save

user output
`1013 110542` view save

Test 17

Verdict: ACCEPTED

input
`200000 11000 144259 147062 129144 34375 27688 122452 149687 178943 ...` view save

correct output
`9 68155 74343 92593 98229 103701...` view save

user output
`9 68155` view save

Test 18

Verdict: ACCEPTED

input
`200000 20000 90535 65281 89691 120083 89310 122019 48389 89987 ...` view save

correct output
`13 31911 56441 62585 103301 11475...` view save

user output
`13 114756` view save

Test 19

Verdict: ACCEPTED

input
`200000 10010 126094 109522 32134 117141 77008 145100 95190 29985 ...` view save

correct output
`841 150165 150222 150264 150414 15...` view save

user output
`841 188392` view save

Test 20

Verdict: ACCEPTED

input
`200000 5000 125110 185897 185897 15293 185897 65525 32273 15293 ...` view save

correct output
`1 120494` view save

user output
`1 120494` view save

Test 21

Verdict: ACCEPTED

input
`200000 10000 29178 72745 65717 29178 86262 72745 28578 72745 ...` view save

correct output
`2 70740 146957` view save

user output
`2 70740` view save

Test 22

Verdict: ACCEPTED

input
`200000 100000 68474 3445 68474 188768 75980 188768 53957 75980 ...` view save

correct output
`1 130925` view save

user output
`1 130925` view save

Test 23

Verdict: ACCEPTED

input
`200000 5000 199775 110116 20398 110116 131291 110116 20398 105072 ...` view save

correct output
`1 142994` view save

user output
`1 142994` view save

Test 24

Verdict: ACCEPTED

input
`200000 10000 14706 98422 143108 14706 183282 14706 177517 14706 ...` view save

correct output
`1 24321` view save

user output
`1 24321` view save

Test 25

Verdict: ACCEPTED

input
`200000 100000 98965 122949 80666 98965 98965 122727 80666 94692 ...` view save

correct output
`1 89572` view save

user output
`1 89572` view save

Test 26

Verdict: ACCEPTED

input
`200000 5000 175908 116198 108345 116198 116198 46371 108738 175908 ...` view save

correct output
`1 104870` view save

user output
`1 104870` view save

Test 27

Verdict: ACCEPTED

input
`200000 10000 72296 103083 173676 72296 72296 191544 38971 72296 ...` view save

correct output
`1 1181` view save

user output
`1 1181` view save

Test 28

Verdict: ACCEPTED

input
`200000 100000 180193 90285 90285 3229 90285 191578 49699 90285 ...` view save

correct output
`1 94989` view save

user output
`1 94989` view save

Test 29

Verdict: ACCEPTED

input
`200000 5000 149895 27443 149895 63596 162631 149895 77710 149895 ...` view save

correct output
`3 9962 69107 158765` view save

user output
`3 69107` view save

Test 30

Verdict: ACCEPTED

input
`200000 10000 48685 181649 181649 86877 161760 181649 27659 181649 ...` view save

correct output
`6 33818 96668 107877 151891 1746...` view save

user output
`6 33818` view save

Test 31

Verdict: ACCEPTED

input
`200000 100000 11743 113918 11743 150916 11743 48160 183097 11743 ...` view save

correct output
`2 3617 191200` view save

user output
`2 191200` view save

Test 32

Verdict: ACCEPTED

input
`200000 10000 99835 74128 188699 111418 188699 179102 88827 164875 ...` view save

correct output
`93707 2 5 7 8 14 15 16 19 22 25 28 3...` view save

user output
`93707 90343` view save

Test 33

Verdict: ACCEPTED

input
`200000 10000 185678 126111 144054 64404 93775 80874 96138 119649 ...` view save

correct output
`2789 41 44 92 148 187 303 372 435 5...` view save

user output
`2789 83978` view save

Test 34

Verdict: ACCEPTED

input
`200000 10000 96298 24580 141435 60260 62879 70753 62879 53651 ...` view save

correct output
`93808 3 4 8 9 10 11 12 13 15 17 19 2...` view save

user output
`93808 183082` view save

Test 35

Verdict: ACCEPTED

input
`200000 10000 66867 107798 69585 26217 142260 2470 170968 66615 ...` view save

correct output
`4 34912 58399 72540 82303` view save

user output
`4 82303` view save

Test 36

Verdict: ACCEPTED

input
`200000 10000 126978 125907 22968 95429 13651 161708 137033 59120 ...` view save

correct output
`93766 3 7 8 10 13 14 16 18 19 24 25 ...` view save

user output
`93766 173415` view save

KILO 2015 2/5

Hacker

Compiler report

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

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Tasks

Submissions (multiply and surrender)