oj.uz

Submission #443012

# Submission time Handle Problem Language Result Execution time Memory
443012 2021-07-09T13:23:07 Z vanic Highway Tolls (IOI18_highway) C++14
51 / 100
 244 ms 16176 KB 
#include "highway.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;

const int maxn=1e5, maxm=2e5;

int m, a, b, n;
vector < int > ms[maxn];
vector < int > ms1[maxn];
pair < int, int > edge[maxm];
vector < int > Q;
ll poc;

int nadji(int l, int r){
	if(l==r-1){
		return l;
	}
	int mid=(l+r)/2;
	for(int i=l; i<mid; i++){
		Q[i]=1;
	}
	ll val=ask(Q);
	if(val>poc){
		for(int i=l; i<mid; i++){
			Q[i]=0;
		}
		return nadji(l, mid);
	}
	else{
		return nadji(mid, r);
	}
	
}

int dist[2][maxn];

void bfs(int x, int ind){
	queue < int > q;
	q.push(x);
	dist[ind][x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(dist[ind][ms[x][i]]==-1  && !Q[ms1[x][i]]){
				dist[ind][ms[x][i]]=dist[ind][x]+1;
				q.push(ms[x][i]);
			}
		}
	}
}

int col[maxn];
vector < int > Q1;  

int bio[maxn];
vector < int > red;

void bfs1(int x){
	queue < int > q;
	q.push(x);
	memset(bio, -1, sizeof(bio));
	bio[x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(bio[ms[x][i]]==-1 && col[ms[x][i]]==col[x] && !Q[ms1[x][i]]){
				bio[ms[x][i]]=bio[x]+1;
				red.push_back(ms1[x][i]);
//				cout << x << ' ' << ms[x][i] << ' ' << ms1[x][i] << endl;
				q.push(ms[x][i]);
			}
		}
	}
}



ll maksi;

int rijesi(int l, int r){
	if(l==r-1){
		return l;
	}
	int mid=(l+r)/2;
	for(int i=mid; i<r; i++){
		if(red[i]==-1){
			continue;
		}
		Q[red[i]]=1;
	}
/*	cout << "querijam " << l << ' ' << r << endl;
	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
//	cout << ask(Q) << endl;
	if(ask(Q)==maksi){
//		cout << "ima" << endl;
		return rijesi(l, mid);
	}
	else{
		for(int i=mid; i<r; i++){
			if(red[i]==-1){
				continue;
			}
			Q[red[i]]=0;
		}
		return rijesi(mid, r);
	}
}

void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
	m = u.size();
	n=N;
	a=A;
	b=B;
	for(int i=0; i<m; i++){
		edge[i]={u[i], v[i]};
		ms[u[i]].push_back(v[i]);
		ms[v[i]].push_back(u[i]);
		ms1[u[i]].push_back(i);
		ms1[v[i]].push_back(i);
	}
	Q.resize(m, 0);
	poc=ask(Q);
	int x=nadji(0, m);

/*	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
	Q1=Q;


	memset(dist[0], -1, sizeof(dist[0]));
	memset(dist[1], -1, sizeof(dist[1]));
	bfs(edge[x].first, 0);
	bfs(edge[x].second, 1);
	for(int i=0; i<n; i++){
		if(dist[0][i]<dist[1][i]){
			col[i]=1;
		}
		else if(dist[0][i]==dist[1][i]){
			col[i]=2;
		}
	}
	red.push_back(-1);
	bfs1(edge[x].first);
	for(int i=0; i<m; i++){
		Q[i]=1;
	}
	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=0;
	}
	maksi=ask(Q);
//	cout << "maksi " << maksi << endl;
/*	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=1;
	}*/
/*	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;
	cout << "red ";
	for(int i=0; i<(int)red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
	int y=red[rijesi(0, red.size())];
	int sol1, sol2;
//	cout << y << endl;
	if(y==-1){
		sol1=edge[x].first;
	}
	else if(bio[edge[y].first]>bio[edge[y].second]){
		sol1=edge[y].first;
	}
	else{
		sol1=edge[y].second;
	}
/*	for(int i=0; i<n; i++){
		sta[i].clear();
		sta1[i].clear();
	}*/
	red.clear();
	red.push_back(-1);
	Q=Q1;
	bfs1(edge[x].second);
	for(int i=0; i<m; i++){
		Q[i]=1;
	}
	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=0;
	}
	maksi=ask(Q);
	
/*	cout << "trazim " << endl;
	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
/*	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=1;
	}*/
/*	cout << "red2 ";
	for(int i=0; i<(int)red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
	y=red[rijesi(0, red.size())];
//	cout << "maksi " << maksi << endl;
//	cout << y << endl;
	if(y==-1){
		sol2=edge[x].second;
	}
	else if(bio[edge[y].first]>bio[edge[y].second]){
		sol2=edge[y].first;
	}
	else{
		sol2=edge[y].second;
	}
//	cout << sol1 << ' ' << sol2 << ' ' << x << endl;
	answer(sol1, sol2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6216 KB Output is correct
2 Correct 21 ms 7264 KB Output is correct
3 Correct 204 ms 15724 KB Output is correct
4 Correct 230 ms 15800 KB Output is correct
5 Correct 211 ms 15736 KB Output is correct
6 Correct 240 ms 15500 KB Output is correct
7 Correct 204 ms 15580 KB Output is correct
8 Correct 202 ms 15832 KB Output is correct
9 Correct 217 ms 15728 KB Output is correct
10 Correct 223 ms 15576 KB Output is correct
11 Correct 222 ms 15088 KB Output is correct
12 Correct 244 ms 15452 KB Output is correct
13 Correct 210 ms 15540 KB Output is correct
14 Correct 211 ms 15624 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7112 KB Output is correct
2 Correct 29 ms 8176 KB Output is correct
3 Correct 48 ms 9108 KB Output is correct
4 Correct 113 ms 15120 KB Output is correct
5 Correct 158 ms 15124 KB Output is correct
6 Correct 146 ms 15228 KB Output is correct
7 Correct 153 ms 15032 KB Output is correct
8 Correct 115 ms 15120 KB Output is correct
9 Correct 138 ms 15228 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6216 KB Output is correct
2 Correct 17 ms 7076 KB Output is correct
3 Correct 174 ms 13784 KB Output is correct
4 Correct 172 ms 15924 KB Output is correct
5 Correct 198 ms 15188 KB Output is correct
6 Correct 160 ms 15268 KB Output is correct
7 Correct 211 ms 15612 KB Output is correct
8 Correct 205 ms 15236 KB Output is correct
9 Correct 227 ms 15728 KB Output is correct
10 Correct 173 ms 15536 KB Output is correct
11 Correct 202 ms 15532 KB Output is correct
12 Correct 191 ms 15420 KB Output is correct
13 Correct 231 ms 15376 KB Output is correct
14 Correct 201 ms 15092 KB Output is correct
15 Correct 149 ms 15312 KB Output is correct
16 Correct 185 ms 15292 KB Output is correct
17 Correct 214 ms 15528 KB Output is correct
18 Correct 229 ms 15528 KB Output is correct
19 Correct 153 ms 15172 KB Output is correct
20 Correct 159 ms 14996 KB Output is correct
21 Correct 171 ms 16176 KB Output is correct
22 Correct 148 ms 15948 KB Output is correct
23 Correct 166 ms 16176 KB Output is correct
24 Correct 184 ms 16108 KB Output is correct
25 Correct 240 ms 15736 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 7232 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 7240 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -