oj.uz

Submission #820045

# Submission time Handle Problem Language Result Execution time Memory
820045 2023-08-10T18:25:35 Z ttamx Highway Tolls (IOI18_highway) C++14
23 / 100
 185 ms 12908 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(int i=1;i<exgroup.size();i++){
			e[get<2>(exgroup[i])]=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:54: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]
   54 |   for(int i=1;i<exgroup.size();i++){
      |               ~^~~~~~~~~~~~~~~
highway.cpp:57: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]
   57 |   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 3 ms 4164 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 4164 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 3 ms 4160 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4216 KB Output is correct
2 Correct 10 ms 4944 KB Output is correct
3 Correct 123 ms 10924 KB Output is correct
4 Correct 115 ms 10948 KB Output is correct
5 Correct 90 ms 10948 KB Output is correct
6 Correct 83 ms 10940 KB Output is correct
7 Correct 130 ms 10944 KB Output is correct
8 Correct 89 ms 10944 KB Output is correct
9 Correct 103 ms 10980 KB Output is correct
10 Correct 91 ms 11172 KB Output is correct
11 Correct 116 ms 10148 KB Output is correct
12 Correct 116 ms 10780 KB Output is correct
13 Correct 103 ms 10392 KB Output is correct
14 Incorrect 97 ms 10408 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 11 ms 4864 KB Output is correct
2 Correct 16 ms 5564 KB Output is correct
3 Correct 29 ms 6280 KB Output is correct
4 Correct 99 ms 10184 KB Output is correct
5 Correct 69 ms 10240 KB Output is correct
6 Correct 125 ms 10532 KB Output is correct
7 Correct 68 ms 10368 KB Output is correct
8 Correct 83 ms 10136 KB Output is correct
9 Incorrect 63 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 10 ms 4848 KB Output is correct
3 Correct 89 ms 9808 KB Output is correct
4 Correct 112 ms 10936 KB Output is correct
5 Correct 82 ms 10876 KB Output is correct
6 Correct 120 ms 10972 KB Output is correct
7 Correct 83 ms 10952 KB Output is correct
8 Correct 100 ms 10968 KB Output is correct
9 Incorrect 106 ms 10952 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 4948 KB Output is correct
2 Correct 18 ms 5072 KB Output is correct
3 Correct 110 ms 11316 KB Output is correct
4 Correct 151 ms 11828 KB Output is correct
5 Correct 145 ms 12776 KB Output is correct
6 Correct 179 ms 12636 KB Output is correct
7 Correct 126 ms 12772 KB Output is correct
8 Correct 134 ms 12508 KB Output is correct
9 Correct 146 ms 10800 KB Output is correct
10 Correct 140 ms 10908 KB Output is correct
11 Correct 146 ms 11440 KB Output is correct
12 Correct 152 ms 12040 KB Output is correct
13 Correct 142 ms 12408 KB Output is correct
14 Correct 152 ms 12552 KB Output is correct
15 Correct 163 ms 12688 KB Output is correct
16 Correct 123 ms 11480 KB Output is correct
17 Correct 100 ms 11180 KB Output is correct
18 Correct 91 ms 11412 KB Output is correct
19 Correct 79 ms 11208 KB Output is correct
20 Correct 84 ms 11296 KB Output is correct
21 Correct 135 ms 12908 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4948 KB Output is correct
2 Correct 16 ms 5072 KB Output is correct
3 Correct 114 ms 11120 KB Output is correct
4 Correct 143 ms 11556 KB Output is correct
5 Correct 113 ms 11660 KB Output is correct
6 Correct 139 ms 12572 KB Output is correct
7 Correct 119 ms 11304 KB Output is correct
8 Correct 150 ms 11484 KB Output is correct
9 Correct 158 ms 11432 KB Output is correct
10 Correct 136 ms 12496 KB Output is correct
11 Correct 151 ms 12716 KB Output is correct
12 Correct 185 ms 12440 KB Output is correct
13 Correct 120 ms 11344 KB Output is correct
14 Correct 93 ms 10928 KB Output is correct
15 Correct 130 ms 11432 KB Output is correct
16 Correct 90 ms 10932 KB Output is correct
17 Correct 97 ms 11392 KB Output is correct
18 Correct 119 ms 10992 KB Output is correct
19 Correct 129 ms 12032 KB Output is correct
20 Correct 131 ms 12500 KB Output is correct
21 Correct 145 ms 12760 KB Output is correct
22 Correct 145 ms 12544 KB Output is correct
23 Correct 127 ms 12476 KB Output is correct
24 Correct 133 ms 12528 KB Output is correct
25 Correct 127 ms 12844 KB Output is correct
26 Correct 159 ms 12844 KB Output is correct
27 Correct 129 ms 11284 KB Output is correct
28 Correct 102 ms 11180 KB Output is correct
29 Correct 98 ms 11428 KB Output is correct
30 Incorrect 75 ms 11240 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -