oj.uz

Submission #820041

# Submission time Handle Problem Language Result Execution time Memory
820041 2023-08-10T18:22:07 Z ttamx Highway Tolls (IOI18_highway) C++14
23 / 100
 193 ms 12948 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)/2;
		e=vector<int>(m,1);
		for(auto x:exgroup)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 4048 KB Output is correct
4 Correct 2 ms 4048 KB Output is correct
5 Correct 2 ms 4160 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 4048 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 9 ms 4996 KB Output is correct
3 Correct 93 ms 10940 KB Output is correct
4 Correct 90 ms 11044 KB Output is correct
5 Correct 101 ms 10932 KB Output is correct
6 Correct 86 ms 10980 KB Output is correct
7 Correct 129 ms 10916 KB Output is correct
8 Correct 113 ms 10972 KB Output is correct
9 Correct 89 ms 10984 KB Output is correct
10 Correct 88 ms 10932 KB Output is correct
11 Correct 128 ms 10152 KB Output is correct
12 Correct 114 ms 10868 KB Output is correct
13 Correct 90 ms 10332 KB Output is correct
14 Incorrect 90 ms 10404 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 12 ms 4944 KB Output is correct
2 Correct 27 ms 5556 KB Output is correct
3 Correct 34 ms 6164 KB Output is correct
4 Correct 85 ms 10264 KB Output is correct
5 Correct 117 ms 10244 KB Output is correct
6 Correct 97 ms 10528 KB Output is correct
7 Correct 107 ms 10292 KB Output is correct
8 Correct 70 ms 10148 KB Output is correct
9 Incorrect 100 ms 10376 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 83 ms 9936 KB Output is correct
4 Correct 112 ms 10856 KB Output is correct
5 Correct 129 ms 10932 KB Output is correct
6 Correct 138 ms 11044 KB Output is correct
7 Correct 81 ms 10932 KB Output is correct
8 Correct 123 ms 10932 KB Output is correct
9 Incorrect 123 ms 10944 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 4816 KB Output is correct
2 Correct 11 ms 5016 KB Output is correct
3 Correct 110 ms 11304 KB Output is correct
4 Correct 182 ms 11828 KB Output is correct
5 Correct 128 ms 12724 KB Output is correct
6 Correct 131 ms 12644 KB Output is correct
7 Correct 186 ms 12772 KB Output is correct
8 Correct 131 ms 12484 KB Output is correct
9 Correct 169 ms 10592 KB Output is correct
10 Correct 90 ms 10980 KB Output is correct
11 Correct 120 ms 11352 KB Output is correct
12 Correct 193 ms 12072 KB Output is correct
13 Correct 124 ms 12284 KB Output is correct
14 Correct 137 ms 12596 KB Output is correct
15 Correct 133 ms 12676 KB Output is correct
16 Correct 133 ms 11512 KB Output is correct
17 Correct 80 ms 11176 KB Output is correct
18 Correct 89 ms 11444 KB Output is correct
19 Correct 82 ms 11220 KB Output is correct
20 Correct 112 ms 11344 KB Output is correct
21 Correct 152 ms 12948 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4944 KB Output is correct
2 Correct 17 ms 5072 KB Output is correct
3 Correct 129 ms 11040 KB Output is correct
4 Correct 132 ms 11572 KB Output is correct
5 Correct 146 ms 11652 KB Output is correct
6 Correct 162 ms 12676 KB Output is correct
7 Correct 108 ms 11312 KB Output is correct
8 Correct 136 ms 11488 KB Output is correct
9 Correct 116 ms 11484 KB Output is correct
10 Correct 123 ms 12636 KB Output is correct
11 Correct 135 ms 12608 KB Output is correct
12 Correct 134 ms 12548 KB Output is correct
13 Correct 96 ms 11432 KB Output is correct
14 Correct 133 ms 10956 KB Output is correct
15 Correct 91 ms 11444 KB Output is correct
16 Correct 91 ms 10940 KB Output is correct
17 Correct 102 ms 11368 KB Output is correct
18 Correct 115 ms 10988 KB Output is correct
19 Correct 144 ms 12044 KB Output is correct
20 Correct 128 ms 12496 KB Output is correct
21 Correct 144 ms 12752 KB Output is correct
22 Correct 153 ms 12548 KB Output is correct
23 Correct 140 ms 12580 KB Output is correct
24 Correct 131 ms 12576 KB Output is correct
25 Correct 140 ms 12848 KB Output is correct
26 Correct 127 ms 12844 KB Output is correct
27 Correct 82 ms 11304 KB Output is correct
28 Correct 102 ms 11132 KB Output is correct
29 Correct 136 ms 11368 KB Output is correct
30 Incorrect 99 ms 11236 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -