oj.uz

Submission #714277

# Submission time Handle Problem Language Result Execution time Memory
714277 2023-03-24T07:45:15 Z alvingogo Highway Tolls (IOI18_highway) C++14
100 / 100
 223 ms 11068 KB 
#include "highway.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct no{
	vector<pair<int,int> > ch;
};
vector<no> v;
int n;
int a,b;
long long dis;
vector<int> chg;
int find_one(int rt,vector<pair<int,int> >& x){
	int l=0,r=(int)(x.size())-1;
	while(r>l){
		int mid=(l+r)/2;
		for(int i=0;i<=mid;i++){
			chg[x[i].sc]=1;
		}
		if(ask(chg)!=dis){
			r=mid;
		}
		else{
			l=mid+1;
		}
		for(int i=0;i<=mid;i++){
			chg[x[i].sc]=0;
		}
	}
	return x[l].fs;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	a=A;
	b=B;
	n=N;
	v.resize(n);
	int m=U.size();
	for(int i=0;i<m;i++){
		v[U[i]].ch.push_back({V[i],i});
		v[V[i]].ch.push_back({U[i],i});
	}
	int l=0,r=m-1;
	chg.resize(m,0);
	dis=ask(chg);
	while(r>l){
		int mid=(l+r)/2;
		for(int i=0;i<=mid;i++){
			chg[i]=1;
		}
		if(ask(chg)==dis){
			l=mid+1;
		}
		else{
			r=mid;
		}
		for(int i=0;i<=mid;i++){
			chg[i]=0;
		}
	}
	//edge = U[l],V[l];
	queue<int> q;
	vector<int> vis(n);
	q.push(U[l]);
	q.push(V[l]);
	vis[U[l]]=1;
	vis[V[l]]=-1;
	vector<pair<int,int> > c,d;
	c.push_back({U[l],-1});
	d.push_back({V[l],-1});
	while(q.size()){
		auto h=q.front();
		q.pop();
		for(auto y:v[h].ch){
			if(!vis[y.fs]){
				vis[y.fs]=vis[h];
				q.push(y.fs);
				if(vis[h]==1){
					c.push_back(y);
				}
				else{
					d.push_back(y);
				}
			}
		}
	}
	fill(chg.begin(),chg.end(),1);
	reverse(c.begin(),c.end());
	reverse(d.begin(),d.end());
	chg[l]=0;
	for(auto h:c){
		if(h.sc<0){
			continue;
		}
		chg[h.sc]=0;
	}
	for(auto h:d){
		if(h.sc<0){
			continue;
		}
		chg[h.sc]=0;
	}
	int e=find_one(U[l],c);
	int f=find_one(V[l],d);
	answer(e,f);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 13 ms 1232 KB Output is correct
3 Correct 138 ms 8984 KB Output is correct
4 Correct 110 ms 8976 KB Output is correct
5 Correct 116 ms 9036 KB Output is correct
6 Correct 101 ms 8968 KB Output is correct
7 Correct 124 ms 9008 KB Output is correct
8 Correct 167 ms 8984 KB Output is correct
9 Correct 100 ms 9072 KB Output is correct
10 Correct 114 ms 9040 KB Output is correct
11 Correct 131 ms 8472 KB Output is correct
12 Correct 106 ms 8628 KB Output is correct
13 Correct 112 ms 8528 KB Output is correct
14 Correct 119 ms 8660 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1232 KB Output is correct
2 Correct 19 ms 2148 KB Output is correct
3 Correct 63 ms 3020 KB Output is correct
4 Correct 121 ms 8284 KB Output is correct
5 Correct 89 ms 8308 KB Output is correct
6 Correct 82 ms 8644 KB Output is correct
7 Correct 83 ms 8488 KB Output is correct
8 Correct 81 ms 8264 KB Output is correct
9 Correct 89 ms 8740 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 11 ms 1248 KB Output is correct
3 Correct 102 ms 7380 KB Output is correct
4 Correct 138 ms 8988 KB Output is correct
5 Correct 138 ms 9068 KB Output is correct
6 Correct 116 ms 8968 KB Output is correct
7 Correct 118 ms 8996 KB Output is correct
8 Correct 113 ms 9068 KB Output is correct
9 Correct 121 ms 9144 KB Output is correct
10 Correct 108 ms 9080 KB Output is correct
11 Correct 119 ms 8492 KB Output is correct
12 Correct 105 ms 8620 KB Output is correct
13 Correct 139 ms 8628 KB Output is correct
14 Correct 148 ms 8244 KB Output is correct
15 Correct 145 ms 9048 KB Output is correct
16 Correct 110 ms 9008 KB Output is correct
17 Correct 111 ms 8652 KB Output is correct
18 Correct 111 ms 8620 KB Output is correct
19 Correct 115 ms 9056 KB Output is correct
20 Correct 109 ms 8512 KB Output is correct
21 Correct 79 ms 9900 KB Output is correct
22 Correct 83 ms 9816 KB Output is correct
23 Correct 117 ms 9396 KB Output is correct
24 Correct 154 ms 9328 KB Output is correct
25 Correct 101 ms 8612 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1308 KB Output is correct
2 Correct 20 ms 1400 KB Output is correct
3 Correct 140 ms 9348 KB Output is correct
4 Correct 171 ms 9912 KB Output is correct
5 Correct 160 ms 11004 KB Output is correct
6 Correct 156 ms 10536 KB Output is correct
7 Correct 166 ms 10584 KB Output is correct
8 Correct 174 ms 10596 KB Output is correct
9 Correct 117 ms 7028 KB Output is correct
10 Correct 122 ms 7464 KB Output is correct
11 Correct 119 ms 8280 KB Output is correct
12 Correct 200 ms 9972 KB Output is correct
13 Correct 172 ms 10312 KB Output is correct
14 Correct 210 ms 10740 KB Output is correct
15 Correct 148 ms 10888 KB Output is correct
16 Correct 144 ms 8364 KB Output is correct
17 Correct 105 ms 9548 KB Output is correct
18 Correct 132 ms 9568 KB Output is correct
19 Correct 90 ms 9536 KB Output is correct
20 Correct 121 ms 9528 KB Output is correct
21 Correct 150 ms 10916 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1260 KB Output is correct
2 Correct 20 ms 1308 KB Output is correct
3 Correct 160 ms 9416 KB Output is correct
4 Correct 136 ms 9632 KB Output is correct
5 Correct 149 ms 9760 KB Output is correct
6 Correct 219 ms 10520 KB Output is correct
7 Correct 109 ms 9360 KB Output is correct
8 Correct 138 ms 9652 KB Output is correct
9 Correct 142 ms 9660 KB Output is correct
10 Correct 180 ms 10688 KB Output is correct
11 Correct 170 ms 10916 KB Output is correct
12 Correct 176 ms 10532 KB Output is correct
13 Correct 170 ms 8344 KB Output is correct
14 Correct 161 ms 7344 KB Output is correct
15 Correct 118 ms 8372 KB Output is correct
16 Correct 150 ms 7364 KB Output is correct
17 Correct 154 ms 8400 KB Output is correct
18 Correct 115 ms 7456 KB Output is correct
19 Correct 172 ms 9676 KB Output is correct
20 Correct 148 ms 10488 KB Output is correct
21 Correct 191 ms 10780 KB Output is correct
22 Correct 223 ms 10564 KB Output is correct
23 Correct 195 ms 10732 KB Output is correct
24 Correct 158 ms 10784 KB Output is correct
25 Correct 197 ms 10984 KB Output is correct
26 Correct 161 ms 11060 KB Output is correct
27 Correct 97 ms 9600 KB Output is correct
28 Correct 96 ms 9432 KB Output is correct
29 Correct 93 ms 9568 KB Output is correct
30 Correct 110 ms 9444 KB Output is correct
31 Correct 120 ms 9532 KB Output is correct
32 Correct 92 ms 9476 KB Output is correct
33 Correct 108 ms 9696 KB Output is correct
34 Correct 132 ms 9632 KB Output is correct
35 Correct 97 ms 9548 KB Output is correct
36 Correct 128 ms 9332 KB Output is correct
37 Correct 140 ms 9632 KB Output is correct
38 Correct 90 ms 9440 KB Output is correct
39 Correct 195 ms 11068 KB Output is correct
40 Correct 182 ms 11004 KB Output is correct
41 Correct 178 ms 10876 KB Output is correct
42 Correct 147 ms 10552 KB Output is correct