oj.uz

Submission #76980

# Submission time Handle Problem Language Result Execution time Memory
76980 2018-09-19T17:51:06 Z gs14004 Highway Tolls (IOI18_highway) C++17
0 / 100
 28 ms 3492 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 90005;

int dist[MAXN];
vector<int> gph[MAXN];

lint cut_ask(int m, vector<int> &c, vector<int> &u, vector<int> &v){
	bitset<MAXN> vis;
	for(auto &i : c) vis[i] = 1;
	vector<int> query(m);
	for(int i=0; i<m; i++){
		if(vis[u[i]] != vis[v[i]]) query[i] = 1;
	}
	return ask(query);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	for(int i=0; i<M; i++){
		gph[U[i]].emplace_back(V[i]);
		gph[V[i]].emplace_back(U[i]); 
	}
	vector<int> v(M);
	int stdist = ask(v) / A;
	int s = 0, e = M;
	while(s + 1 != e){
		int m = (s + e) / 2;
		fill(v.begin(), v.end(), 1);
		fill(v.begin() + s, v.begin() + m, 0);
		if(ask(v) <= 1ll * B * (stdist - 1) + A) s = m; // no intersection
		else e = m;
	}
	// 18 queries till this point
	vector<int> bord[2];
	queue<pi> que;
	que.emplace(0, U[s]);
	que.emplace(1, V[s]);
	memset(dist, 0x3f, sizeof(dist));
	dist[U[s]] = dist[V[s]] = 0;
	while(!que.empty()){
		auto x = que.front(); que.pop();
		bord[x.first].push_back(x.second);
		for(auto &i : gph[x.second]){
			if(dist[i] > dist[x.second] + 1){
				dist[i] = dist[x.second] + 1;
				que.emplace(x.first, i);
			}
		}
	}
	s = 0, e = (int)bord[0].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[0].begin() + m, bord[0].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int S = bord[0][s];
	s = 0, e = (int)bord[1].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[1].begin() + m, bord[1].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int T = bord[1][s];
	answer(S, T);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3492 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 21 ms 3476 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -