oj.uz

Submission #820064

# Submission time Handle Problem Language Result Execution time Memory
820064 2023-08-10T18:45:27 Z ttamx Highway Tolls (IOI18_highway) C++14
23 / 100
 192 ms 12932 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];
int 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: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 4164 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 4048 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 KB Output is correct
2 Correct 10 ms 4988 KB Output is correct
3 Correct 110 ms 10940 KB Output is correct
4 Correct 102 ms 10980 KB Output is correct
5 Correct 89 ms 10956 KB Output is correct
6 Correct 101 ms 10896 KB Output is correct
7 Correct 95 ms 10948 KB Output is correct
8 Correct 89 ms 10976 KB Output is correct
9 Correct 120 ms 10944 KB Output is correct
10 Correct 112 ms 10964 KB Output is correct
11 Correct 102 ms 10196 KB Output is correct
12 Correct 95 ms 10768 KB Output is correct
13 Correct 138 ms 10380 KB Output is correct
14 Incorrect 142 ms 10420 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4944 KB Output is correct
2 Correct 16 ms 5572 KB Output is correct
3 Correct 23 ms 6160 KB Output is correct
4 Correct 74 ms 10224 KB Output is correct
5 Correct 69 ms 10204 KB Output is correct
6 Correct 69 ms 10556 KB Output is correct
7 Correct 97 ms 10364 KB Output is correct
8 Correct 105 ms 10136 KB Output is correct
9 Incorrect 95 ms 10396 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 KB Output is correct
2 Correct 12 ms 4944 KB Output is correct
3 Correct 78 ms 9800 KB Output is correct
4 Correct 125 ms 10964 KB Output is correct
5 Correct 96 ms 10912 KB Output is correct
6 Correct 106 ms 10968 KB Output is correct
7 Correct 108 ms 10980 KB Output is correct
8 Correct 119 ms 11092 KB Output is correct
9 Incorrect 87 ms 10988 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4932 KB Output is correct
2 Correct 15 ms 5072 KB Output is correct
3 Correct 117 ms 11316 KB Output is correct
4 Correct 120 ms 11860 KB Output is correct
5 Correct 171 ms 12732 KB Output is correct
6 Correct 129 ms 12648 KB Output is correct
7 Correct 154 ms 12764 KB Output is correct
8 Correct 166 ms 12476 KB Output is correct
9 Correct 89 ms 10488 KB Output is correct
10 Correct 94 ms 10924 KB Output is correct
11 Correct 92 ms 11376 KB Output is correct
12 Correct 138 ms 12032 KB Output is correct
13 Correct 123 ms 12280 KB Output is correct
14 Correct 169 ms 12592 KB Output is correct
15 Correct 144 ms 12684 KB Output is correct
16 Correct 146 ms 11436 KB Output is correct
17 Correct 77 ms 11176 KB Output is correct
18 Correct 90 ms 11440 KB Output is correct
19 Correct 88 ms 11248 KB Output is correct
20 Correct 85 ms 11388 KB Output is correct
21 Correct 180 ms 12932 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4944 KB Output is correct
2 Correct 11 ms 5072 KB Output is correct
3 Correct 157 ms 11076 KB Output is correct
4 Correct 127 ms 11572 KB Output is correct
5 Correct 125 ms 11720 KB Output is correct
6 Correct 154 ms 12572 KB Output is correct
7 Correct 100 ms 11452 KB Output is correct
8 Correct 101 ms 11500 KB Output is correct
9 Correct 167 ms 11480 KB Output is correct
10 Correct 127 ms 12492 KB Output is correct
11 Correct 191 ms 12680 KB Output is correct
12 Correct 154 ms 12520 KB Output is correct
13 Correct 105 ms 11424 KB Output is correct
14 Correct 114 ms 10952 KB Output is correct
15 Correct 93 ms 11456 KB Output is correct
16 Correct 117 ms 10936 KB Output is correct
17 Correct 93 ms 11364 KB Output is correct
18 Correct 101 ms 10984 KB Output is correct
19 Correct 134 ms 12096 KB Output is correct
20 Correct 171 ms 12492 KB Output is correct
21 Correct 137 ms 12752 KB Output is correct
22 Correct 158 ms 12544 KB Output is correct
23 Correct 159 ms 12584 KB Output is correct
24 Correct 192 ms 12552 KB Output is correct
25 Correct 138 ms 12844 KB Output is correct
26 Correct 132 ms 12844 KB Output is correct
27 Correct 91 ms 11416 KB Output is correct
28 Correct 102 ms 11228 KB Output is correct
29 Correct 81 ms 11368 KB Output is correct
30 Incorrect 101 ms 11300 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -