oj.uz

Submission #820070

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

using namespace std;

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];
long long 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)/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)r=mid;
		else l=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:29:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   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:55: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]
   55 |   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 4164 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 4160 KB Output is correct
8 Correct 2 ms 4048 KB Output is correct
9 Correct 2 ms 4044 KB Output is correct
10 Correct 2 ms 4048 KB Output is correct
11 Correct 2 ms 4160 KB Output is correct
12 Correct 2 ms 4048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 KB Output is correct
2 Correct 9 ms 4984 KB Output is correct
3 Correct 89 ms 10932 KB Output is correct
4 Correct 101 ms 10952 KB Output is correct
5 Correct 126 ms 10948 KB Output is correct
6 Correct 114 ms 10944 KB Output is correct
7 Correct 115 ms 10896 KB Output is correct
8 Correct 93 ms 11060 KB Output is correct
9 Correct 85 ms 10984 KB Output is correct
10 Correct 113 ms 10876 KB Output is correct
11 Correct 126 ms 10140 KB Output is correct
12 Correct 108 ms 10764 KB Output is correct
13 Correct 96 ms 10332 KB Output is correct
14 Correct 94 ms 10340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4944 KB Output is correct
2 Correct 17 ms 5540 KB Output is correct
3 Correct 22 ms 6192 KB Output is correct
4 Correct 66 ms 10248 KB Output is correct
5 Correct 78 ms 10272 KB Output is correct
6 Correct 93 ms 10540 KB Output is correct
7 Correct 92 ms 10284 KB Output is correct
8 Correct 73 ms 10136 KB Output is correct
9 Correct 122 ms 10444 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4208 KB Output is correct
2 Correct 12 ms 4944 KB Output is correct
3 Correct 82 ms 9812 KB Output is correct
4 Correct 83 ms 10972 KB Output is correct
5 Correct 88 ms 10936 KB Output is correct
6 Correct 113 ms 10968 KB Output is correct
7 Correct 97 ms 10944 KB Output is correct
8 Correct 106 ms 10848 KB Output is correct
9 Correct 91 ms 10948 KB Output is correct
10 Correct 111 ms 10888 KB Output is correct
11 Correct 131 ms 10324 KB Output is correct
12 Correct 113 ms 10556 KB Output is correct
13 Correct 103 ms 10824 KB Output is correct
14 Correct 116 ms 10176 KB Output is correct
15 Correct 91 ms 10976 KB Output is correct
16 Correct 128 ms 10980 KB Output is correct
17 Correct 96 ms 10400 KB Output is correct
18 Correct 110 ms 10328 KB Output is correct
19 Correct 87 ms 10956 KB Output is correct
20 Correct 107 ms 10340 KB Output is correct
21 Correct 78 ms 11632 KB Output is correct
22 Correct 109 ms 11808 KB Output is correct
23 Correct 89 ms 11152 KB Output is correct
24 Correct 105 ms 10956 KB Output is correct
25 Correct 111 ms 10544 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4944 KB Output is correct
2 Correct 12 ms 5060 KB Output is correct
3 Correct 108 ms 11308 KB Output is correct
4 Correct 149 ms 11836 KB Output is correct
5 Correct 217 ms 12740 KB Output is correct
6 Correct 127 ms 12652 KB Output is correct
7 Correct 133 ms 12756 KB Output is correct
8 Correct 154 ms 12524 KB Output is correct
9 Correct 115 ms 10608 KB Output is correct
10 Correct 91 ms 10968 KB Output is correct
11 Correct 127 ms 11456 KB Output is correct
12 Correct 132 ms 12076 KB Output is correct
13 Correct 149 ms 12288 KB Output is correct
14 Correct 183 ms 12548 KB Output is correct
15 Correct 146 ms 12748 KB Output is correct
16 Correct 122 ms 11488 KB Output is correct
17 Correct 93 ms 11180 KB Output is correct
18 Correct 125 ms 11408 KB Output is correct
19 Correct 118 ms 11272 KB Output is correct
20 Correct 134 ms 11308 KB Output is correct
21 Correct 128 ms 12876 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4932 KB Output is correct
2 Correct 11 ms 5056 KB Output is correct
3 Correct 116 ms 11144 KB Output is correct
4 Correct 117 ms 11556 KB Output is correct
5 Correct 121 ms 11660 KB Output is correct
6 Correct 203 ms 12680 KB Output is correct
7 Correct 111 ms 11336 KB Output is correct
8 Correct 127 ms 11456 KB Output is correct
9 Correct 124 ms 11452 KB Output is correct
10 Correct 123 ms 12444 KB Output is correct
11 Correct 148 ms 12716 KB Output is correct
12 Correct 134 ms 12424 KB Output is correct
13 Correct 163 ms 11484 KB Output is correct
14 Correct 95 ms 10984 KB Output is correct
15 Correct 103 ms 11452 KB Output is correct
16 Correct 136 ms 10936 KB Output is correct
17 Correct 127 ms 11440 KB Output is correct
18 Correct 147 ms 11064 KB Output is correct
19 Correct 125 ms 12052 KB Output is correct
20 Correct 135 ms 12492 KB Output is correct
21 Correct 178 ms 12880 KB Output is correct
22 Correct 130 ms 12552 KB Output is correct
23 Correct 191 ms 12456 KB Output is correct
24 Correct 175 ms 12556 KB Output is correct
25 Correct 131 ms 12840 KB Output is correct
26 Correct 134 ms 12864 KB Output is correct
27 Correct 80 ms 11304 KB Output is correct
28 Correct 82 ms 11172 KB Output is correct
29 Correct 96 ms 11448 KB Output is correct
30 Correct 91 ms 11296 KB Output is correct
31 Correct 98 ms 11256 KB Output is correct
32 Correct 114 ms 11176 KB Output is correct
33 Correct 132 ms 11380 KB Output is correct
34 Correct 106 ms 11368 KB Output is correct
35 Correct 82 ms 11268 KB Output is correct
36 Correct 85 ms 11084 KB Output is correct
37 Correct 88 ms 11324 KB Output is correct
38 Correct 91 ms 11240 KB Output is correct
39 Correct 144 ms 13076 KB Output is correct
40 Correct 175 ms 12888 KB Output is correct
41 Correct 130 ms 12672 KB Output is correct
42 Correct 148 ms 12832 KB Output is correct