oj.uz

Submission #1060499

# Submission time Handle Problem Language Result Execution time Memory
1060499 2024-08-15T16:22:01 Z jamjanek Highway Tolls (IOI18_highway) C++14
100 / 100
 151 ms 11900 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
long long dist;
int odl[90010][5];
vector<int>graf[90010];
void bfs(int start, int war){
	queue<int>kolejka;
	odl[start][war] = 1;
	kolejka.push(start);
	while(kolejka.size()){
		auto x = kolejka.front();
		kolejka.pop();
		for(auto j: graf[x])
			if(!odl[j][war]){
				odl[j][war] = odl[x][war]+1;
				kolejka.push(j);
			}
	}
}
bool cmp1(int a, int b){
	return odl[a][0] < odl[b][0];
}
bool cmp2(int a, int b){
	return odl[a][1] < odl[b][1];
}
vector<int>w;
vector<int>u, v;
bool czy[90010];

void ustaw(int n, vector<int>&zbior, int sufix){
	for(int i=0;i<n;i++)czy[i] = 0;
	for(int j=0;j<(int)zbior.size();j++)czy[zbior[j]] = j>=sufix;
	for(int i=0;i<(int)w.size();i++)
		w[i] = czy[u[i]]|czy[v[i]];
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	u = U, v = V;
	int m = U.size(), i;
	w.resize(m, 0);
	dist = ask(w);
	int pocz = -1, kon = m, srodek;
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		for(i=0;i<m;i++)
			w[i] = (i>=srodek);
		if(dist==ask(w)){
			kon = srodek-1;
		}
		else
			pocz = srodek;
		
	}
	for(i=0;i<m;i++){
		graf[U[i]].push_back(V[i]);
		graf[V[i]].push_back(U[i]);
	}
	//krawedz to jest pocz
	bfs(U[pocz], 0);
	bfs(V[pocz], 1);
//	printf("%d %d\n", U[pocz], V[pocz]);
	vector<int>zbior1, zbior2;
	for(i=0;i<n;i++)
		if(odl[i][0]<odl[i][1])
			zbior1.push_back(i);
	for(i=0;i<n;i++)
		if(odl[i][0]>odl[i][1])
			zbior2.push_back(i);
	sort(zbior1.begin(), zbior1.end(), cmp1);
	sort(zbior2.begin(), zbior2.end(), cmp2);
	
//	for(auto j: zbior1)printf("%d ", j);printf("\n");
//	for(auto j: zbior2)printf("%d ", j);printf("\n");
	
	pocz = -1, kon = zbior1.size();
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		ustaw(n, zbior1, srodek);
		if(dist==ask(w))
			kon = srodek - 1;
		else
			pocz = srodek;
	}
	int S = zbior1[pocz];

	pocz = -1, kon = zbior2.size();
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		ustaw(n, zbior2, srodek);
		if(dist==ask(w))
			kon = srodek - 1;
		else
			pocz = srodek;
		
//		for(auto j: w)printf("%d ", j);printf("\n");
//		printf("%d %d %d\n", pocz, kon, srodek);
	}
	int E = zbior2[pocz];
//	printf("%d %d\n", S, E);
	answer(S, E);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 9 ms 3416 KB Output is correct
3 Correct 102 ms 10320 KB Output is correct
4 Correct 90 ms 10292 KB Output is correct
5 Correct 100 ms 10292 KB Output is correct
6 Correct 88 ms 10504 KB Output is correct
7 Correct 81 ms 10296 KB Output is correct
8 Correct 101 ms 10284 KB Output is correct
9 Correct 91 ms 10416 KB Output is correct
10 Correct 84 ms 10284 KB Output is correct
11 Correct 98 ms 10160 KB Output is correct
12 Correct 112 ms 10284 KB Output is correct
13 Correct 93 ms 10168 KB Output is correct
14 Correct 94 ms 10284 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3416 KB Output is correct
2 Correct 16 ms 4132 KB Output is correct
3 Correct 25 ms 5144 KB Output is correct
4 Correct 71 ms 10168 KB Output is correct
5 Correct 77 ms 10324 KB Output is correct
6 Correct 70 ms 10144 KB Output is correct
7 Correct 67 ms 10148 KB Output is correct
8 Correct 70 ms 10088 KB Output is correct
9 Correct 77 ms 10176 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 8 ms 3416 KB Output is correct
3 Correct 63 ms 8632 KB Output is correct
4 Correct 88 ms 10404 KB Output is correct
5 Correct 81 ms 10280 KB Output is correct
6 Correct 81 ms 10300 KB Output is correct
7 Correct 80 ms 10308 KB Output is correct
8 Correct 89 ms 10304 KB Output is correct
9 Correct 107 ms 10284 KB Output is correct
10 Correct 91 ms 10288 KB Output is correct
11 Correct 96 ms 10160 KB Output is correct
12 Correct 91 ms 10164 KB Output is correct
13 Correct 103 ms 10168 KB Output is correct
14 Correct 98 ms 10172 KB Output is correct
15 Correct 84 ms 10284 KB Output is correct
16 Correct 99 ms 10296 KB Output is correct
17 Correct 98 ms 10172 KB Output is correct
18 Correct 94 ms 10544 KB Output is correct
19 Correct 85 ms 10300 KB Output is correct
20 Correct 96 ms 10204 KB Output is correct
21 Correct 75 ms 10524 KB Output is correct
22 Correct 80 ms 10632 KB Output is correct
23 Correct 78 ms 10700 KB Output is correct
24 Correct 85 ms 10864 KB Output is correct
25 Correct 96 ms 10296 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3416 KB Output is correct
2 Correct 10 ms 3416 KB Output is correct
3 Correct 105 ms 10524 KB Output is correct
4 Correct 100 ms 10944 KB Output is correct
5 Correct 124 ms 11900 KB Output is correct
6 Correct 143 ms 11668 KB Output is correct
7 Correct 129 ms 11644 KB Output is correct
8 Correct 131 ms 11552 KB Output is correct
9 Correct 95 ms 8664 KB Output is correct
10 Correct 95 ms 8872 KB Output is correct
11 Correct 98 ms 9212 KB Output is correct
12 Correct 151 ms 10740 KB Output is correct
13 Correct 125 ms 11100 KB Output is correct
14 Correct 143 ms 11376 KB Output is correct
15 Correct 122 ms 11592 KB Output is correct
16 Correct 110 ms 9480 KB Output is correct
17 Correct 83 ms 10664 KB Output is correct
18 Correct 85 ms 10728 KB Output is correct
19 Correct 76 ms 10644 KB Output is correct
20 Correct 81 ms 10776 KB Output is correct
21 Correct 126 ms 11584 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3416 KB Output is correct
2 Correct 12 ms 3416 KB Output is correct
3 Correct 109 ms 10656 KB Output is correct
4 Correct 109 ms 10724 KB Output is correct
5 Correct 105 ms 10908 KB Output is correct
6 Correct 125 ms 11584 KB Output is correct
7 Correct 104 ms 10608 KB Output is correct
8 Correct 108 ms 10936 KB Output is correct
9 Correct 96 ms 10976 KB Output is correct
10 Correct 125 ms 11512 KB Output is correct
11 Correct 128 ms 11640 KB Output is correct
12 Correct 122 ms 11548 KB Output is correct
13 Correct 103 ms 9324 KB Output is correct
14 Correct 107 ms 8904 KB Output is correct
15 Correct 95 ms 9668 KB Output is correct
16 Correct 102 ms 8924 KB Output is correct
17 Correct 109 ms 9212 KB Output is correct
18 Correct 102 ms 8912 KB Output is correct
19 Correct 128 ms 10676 KB Output is correct
20 Correct 128 ms 11056 KB Output is correct
21 Correct 122 ms 11424 KB Output is correct
22 Correct 134 ms 11456 KB Output is correct
23 Correct 144 ms 11428 KB Output is correct
24 Correct 128 ms 11544 KB Output is correct
25 Correct 125 ms 11416 KB Output is correct
26 Correct 135 ms 11448 KB Output is correct
27 Correct 80 ms 10708 KB Output is correct
28 Correct 87 ms 11232 KB Output is correct
29 Correct 84 ms 10808 KB Output is correct
30 Correct 83 ms 10736 KB Output is correct
31 Correct 87 ms 11136 KB Output is correct
32 Correct 82 ms 10648 KB Output is correct
33 Correct 86 ms 10796 KB Output is correct
34 Correct 88 ms 10884 KB Output is correct
35 Correct 83 ms 10668 KB Output is correct
36 Correct 100 ms 10672 KB Output is correct
37 Correct 96 ms 10768 KB Output is correct
38 Correct 84 ms 10832 KB Output is correct
39 Correct 135 ms 11488 KB Output is correct
40 Correct 129 ms 11484 KB Output is correct
41 Correct 129 ms 11688 KB Output is correct
42 Correct 136 ms 11504 KB Output is correct