oj.uz

Submission #76979

# Submission time Handle Problem Language Result Execution time Memory
76979 2018-09-19T17:48:22 Z gs14004 Highway Tolls (IOI18_highway) C++17
0 / 100
 329 ms 9724 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 Correct 4 ms 2696 KB Output is correct
2 Correct 5 ms 2732 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Incorrect 4 ms 2692 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 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 15 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 5 ms 2868 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 Correct 28 ms 3492 KB Output is correct
2 Correct 29 ms 3520 KB Output is correct
3 Correct 236 ms 8952 KB Output is correct
4 Correct 244 ms 9184 KB Output is correct
5 Correct 315 ms 9676 KB Output is correct
6 Correct 329 ms 9716 KB Output is correct
7 Correct 297 ms 9724 KB Output is correct
8 Correct 295 ms 9612 KB Output is correct
9 Correct 233 ms 7836 KB Output is correct
10 Correct 274 ms 8424 KB Output is correct
11 Correct 278 ms 8428 KB Output is correct
12 Correct 300 ms 9280 KB Output is correct
13 Incorrect 290 ms 9336 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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