oj.uz

Submission #820067

# Submission time Handle Problem Language Result Execution time Memory
820067 2023-08-10T18:46:37 Z ttamx Highway Tolls (IOI18_highway) C++14
100 / 100
 189 ms 13076 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> p2;
typedef tuple<int,int,int> t3;

const int N=90005;
const int M=130005;

int n,m,a,b;
vector<int> e;
vector<int> edge1(M),edge2(M),dist1(N),dist2(N);
vector<p2> adj[N];
ll cost;
vector<t3> group1,group2;
int type[M];
int mainedge;

void bfs(int st,vector<int> &dist,vector<int> &edge){
	queue<int> q;
	edge[st]=-1;
	dist[st]=1;
	q.emplace(st);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto [v,id]:adj[u]){
			if(dist[v])continue;
			edge[v]=id;
			dist[v]=dist[u]+1;
			q.emplace(v);
		}
	}
}

int sol1(){
	int l=0,r=m-1;
	while(l<r){
		int mid=(l+r)/2;
		for(int i=0;i<m;i++)e[i]=i<=mid;
		if(ask(e)!=cost)r=mid;
		else l=mid+1;
	}
	return l;
}

int sol2(vector<t3> &ingroup,vector<t3> &exgroup){
	int l=0,r=ingroup.size()-1;
	while(l<r){
		int mid=(l+r+1)/2;
		e=vector<int>(m,1);
		for(auto x:exgroup)if(get<2>(x)!=-1)e[get<2>(x)]=0;
		for(int i=1;i<ingroup.size();i++){
			e[get<2>(ingroup[i])]=i>=mid;
		}
		e[mainedge]=0;
		if(ask(e)!=cost)l=mid;
		else r=mid-1;
	}
	return get<1>(ingroup[l]);
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
	a=A,b=B;
	m=U.size();
	for(int i=0;i<m;i++){
		int u=U[i],v=V[i];
		adj[u].emplace_back(v,i);
		adj[v].emplace_back(u,i);
	}
	e=vector<int>(m,0);
	cost=ask(e);
	mainedge=sol1();
	int st1=U[mainedge];
	int st2=V[mainedge];
	bfs(st1,dist1,edge1);
	bfs(st2,dist2,edge2);
	for(int i=0;i<n;i++){
		if(dist1[i]<dist2[i])group1.emplace_back(dist1[i],i,edge1[i]);
		if(dist2[i]<dist1[i])group2.emplace_back(dist2[i],i,edge2[i]);
	}
	sort(group1.begin(),group1.end());
	sort(group2.begin(),group2.end());
	int ans1=sol2(group1,group2);
	int ans2=sol2(group2,group1);
	answer(ans1,ans2);
}

Compilation message

highway.cpp: In function 'void bfs(int, std::vector<int>&, std::vector<int>&)':
highway.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |   for(auto [v,id]:adj[u]){
      |            ^
highway.cpp: In function 'int sol2(std::vector<std::tuple<int, int, int> >&, std::vector<std::tuple<int, int, int> >&)':
highway.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=1;i<ingroup.size();i++){
      |               ~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4208 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct
3 Correct 92 ms 10944 KB Output is correct
4 Correct 108 ms 10940 KB Output is correct
5 Correct 132 ms 10956 KB Output is correct
6 Correct 77 ms 10960 KB Output is correct
7 Correct 87 ms 10964 KB Output is correct
8 Correct 91 ms 10944 KB Output is correct
9 Correct 85 ms 10988 KB Output is correct
10 Correct 102 ms 10984 KB Output is correct
11 Correct 97 ms 10148 KB Output is correct
12 Correct 105 ms 10776 KB Output is correct
13 Correct 95 ms 10388 KB Output is correct
14 Correct 124 ms 10396 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4924 KB Output is correct
2 Correct 15 ms 5560 KB Output is correct
3 Correct 19 ms 6192 KB Output is correct
4 Correct 69 ms 10260 KB Output is correct
5 Correct 75 ms 10156 KB Output is correct
6 Correct 67 ms 10608 KB Output is correct
7 Correct 62 ms 10296 KB Output is correct
8 Correct 69 ms 10136 KB Output is correct
9 Correct 68 ms 10268 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 KB Output is correct
2 Correct 11 ms 4944 KB Output is correct
3 Correct 78 ms 9748 KB Output is correct
4 Correct 115 ms 10968 KB Output is correct
5 Correct 85 ms 10908 KB Output is correct
6 Correct 82 ms 10984 KB Output is correct
7 Correct 97 ms 10924 KB Output is correct
8 Correct 80 ms 10908 KB Output is correct
9 Correct 116 ms 10916 KB Output is correct
10 Correct 101 ms 10912 KB Output is correct
11 Correct 102 ms 10380 KB Output is correct
12 Correct 106 ms 10492 KB Output is correct
13 Correct 92 ms 10764 KB Output is correct
14 Correct 108 ms 10208 KB Output is correct
15 Correct 104 ms 10980 KB Output is correct
16 Correct 83 ms 10984 KB Output is correct
17 Correct 90 ms 10352 KB Output is correct
18 Correct 93 ms 10388 KB Output is correct
19 Correct 82 ms 11000 KB Output is correct
20 Correct 132 ms 10420 KB Output is correct
21 Correct 127 ms 11648 KB Output is correct
22 Correct 101 ms 11708 KB Output is correct
23 Correct 92 ms 11208 KB Output is correct
24 Correct 87 ms 10948 KB Output is correct
25 Correct 92 ms 10496 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4888 KB Output is correct
2 Correct 12 ms 5020 KB Output is correct
3 Correct 124 ms 11300 KB Output is correct
4 Correct 156 ms 11836 KB Output is correct
5 Correct 133 ms 12708 KB Output is correct
6 Correct 177 ms 12656 KB Output is correct
7 Correct 129 ms 12776 KB Output is correct
8 Correct 189 ms 12528 KB Output is correct
9 Correct 85 ms 10572 KB Output is correct
10 Correct 111 ms 10956 KB Output is correct
11 Correct 111 ms 11436 KB Output is correct
12 Correct 169 ms 12044 KB Output is correct
13 Correct 150 ms 12224 KB Output is correct
14 Correct 133 ms 12516 KB Output is correct
15 Correct 152 ms 12680 KB Output is correct
16 Correct 122 ms 11492 KB Output is correct
17 Correct 79 ms 11184 KB Output is correct
18 Correct 97 ms 11396 KB Output is correct
19 Correct 108 ms 11208 KB Output is correct
20 Correct 85 ms 11328 KB Output is correct
21 Correct 138 ms 12968 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4852 KB Output is correct
2 Correct 14 ms 5012 KB Output is correct
3 Correct 110 ms 11112 KB Output is correct
4 Correct 180 ms 11584 KB Output is correct
5 Correct 126 ms 11736 KB Output is correct
6 Correct 144 ms 12572 KB Output is correct
7 Correct 119 ms 11336 KB Output is correct
8 Correct 110 ms 11448 KB Output is correct
9 Correct 124 ms 11488 KB Output is correct
10 Correct 128 ms 12516 KB Output is correct
11 Correct 189 ms 12608 KB Output is correct
12 Correct 162 ms 12524 KB Output is correct
13 Correct 88 ms 11476 KB Output is correct
14 Correct 145 ms 10960 KB Output is correct
15 Correct 136 ms 11416 KB Output is correct
16 Correct 125 ms 10956 KB Output is correct
17 Correct 95 ms 11468 KB Output is correct
18 Correct 94 ms 10984 KB Output is correct
19 Correct 124 ms 12032 KB Output is correct
20 Correct 144 ms 12488 KB Output is correct
21 Correct 134 ms 12756 KB Output is correct
22 Correct 164 ms 12528 KB Output is correct
23 Correct 143 ms 12508 KB Output is correct
24 Correct 132 ms 12560 KB Output is correct
25 Correct 179 ms 12836 KB Output is correct
26 Correct 158 ms 12844 KB Output is correct
27 Correct 88 ms 11288 KB Output is correct
28 Correct 107 ms 11176 KB Output is correct
29 Correct 111 ms 11372 KB Output is correct
30 Correct 108 ms 11236 KB Output is correct
31 Correct 101 ms 11200 KB Output is correct
32 Correct 85 ms 11220 KB Output is correct
33 Correct 123 ms 11460 KB Output is correct
34 Correct 85 ms 11332 KB Output is correct
35 Correct 104 ms 11252 KB Output is correct
36 Correct 85 ms 11076 KB Output is correct
37 Correct 90 ms 11332 KB Output is correct
38 Correct 106 ms 11236 KB Output is correct
39 Correct 157 ms 13076 KB Output is correct
40 Correct 134 ms 12912 KB Output is correct
41 Correct 124 ms 12664 KB Output is correct
42 Correct 154 ms 12724 KB Output is correct