oj.uz

Submission #799348

# Submission time Handle Problem Language Result Execution time Memory
799348 2023-07-31T13:07:01 Z NothingXD Highway Tolls (IOI18_highway) C++17
51 / 100
 155 ms 18348 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, m, h[maxn], par[maxn], st[maxn], ver[maxn], tme, edge[maxn][2], cnt;
vector<int> g[maxn], t[maxn];
bool mark[maxn];

void bfs(int V){
	memset(h, -1, sizeof h);
	memset(par, -1, sizeof par);
	memset(mark, true, sizeof mark);
	queue<int> q;
	q.push(V);
	tme = 0;
	h[V] = 0;
	st[V] = 0;
	ver[0] = V;
	while(!q.empty()){
		int v = q.front();	
		//debug(v, h[v], par[v], st[v], ver[st[v]]);
		q.pop();
		for (auto x: g[v]){
			int u = edge[x][0]^edge[x][1]^v;
			if (h[u] == -1){
				h[u] = h[v] + 1;
				par[u] = x;
				st[u] = ++tme;
				ver[tme] = u;
				mark[x] = false;
				q.push(u);
			}
		}
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++){
		edge[i][0] = U[i];
		edge[i][1] = V[i];
		g[U[i]].push_back(i);
		g[V[i]].push_back(i);
	}

	vector<int> q(m, 0);
	ll dis = ask(q);
	int l = -1, r = n-1;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
		for (int i = 0; i < n; i++){
			for (auto x: g[i]){
				q[x] = 1;
			}
		}
		if (ask(q) == dis) l = mid;
		else r = mid;
	}
//	debug(r);
	bfs(r);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = n;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < n; i++){
			q[par[ver[i]]] = 1;
		}
	//	for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
	int S = ver[l];
	bfs(S);
//	debug(S);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = n;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < n; i++){
			q[par[ver[i]]] = 1;
		}
		//for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
	//debug(ver[l]);
	answer(S, ver[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11472 KB Output is correct
2 Correct 6 ms 11472 KB Output is correct
3 Correct 6 ms 11412 KB Output is correct
4 Correct 6 ms 11472 KB Output is correct
5 Correct 6 ms 11472 KB Output is correct
6 Correct 5 ms 11472 KB Output is correct
7 Correct 5 ms 11376 KB Output is correct
8 Correct 5 ms 11372 KB Output is correct
9 Correct 5 ms 11472 KB Output is correct
10 Correct 5 ms 11472 KB Output is correct
11 Correct 6 ms 11472 KB Output is correct
12 Correct 5 ms 11472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11428 KB Output is correct
2 Correct 14 ms 12112 KB Output is correct
3 Correct 155 ms 18168 KB Output is correct
4 Correct 111 ms 17948 KB Output is correct
5 Correct 134 ms 18116 KB Output is correct
6 Correct 109 ms 17940 KB Output is correct
7 Correct 118 ms 17960 KB Output is correct
8 Correct 111 ms 17960 KB Output is correct
9 Correct 136 ms 17960 KB Output is correct
10 Correct 108 ms 18000 KB Output is correct
11 Correct 104 ms 17800 KB Output is correct
12 Correct 122 ms 17964 KB Output is correct
13 Correct 129 ms 17808 KB Output is correct
14 Correct 121 ms 17812 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 25 ms 12840 KB Output is correct
3 Correct 32 ms 13560 KB Output is correct
4 Correct 95 ms 17800 KB Output is correct
5 Correct 97 ms 17872 KB Output is correct
6 Correct 77 ms 17800 KB Output is correct
7 Correct 102 ms 17820 KB Output is correct
8 Correct 68 ms 17836 KB Output is correct
9 Correct 109 ms 17816 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11472 KB Output is correct
2 Correct 16 ms 12136 KB Output is correct
3 Correct 87 ms 16740 KB Output is correct
4 Correct 106 ms 17948 KB Output is correct
5 Correct 122 ms 17956 KB Output is correct
6 Correct 107 ms 17960 KB Output is correct
7 Correct 117 ms 17956 KB Output is correct
8 Correct 105 ms 17952 KB Output is correct
9 Correct 151 ms 17952 KB Output is correct
10 Correct 115 ms 17956 KB Output is correct
11 Correct 107 ms 17804 KB Output is correct
12 Correct 141 ms 17816 KB Output is correct
13 Correct 131 ms 17800 KB Output is correct
14 Correct 126 ms 17820 KB Output is correct
15 Correct 112 ms 17960 KB Output is correct
16 Correct 116 ms 17944 KB Output is correct
17 Correct 110 ms 17812 KB Output is correct
18 Correct 112 ms 17808 KB Output is correct
19 Correct 128 ms 17948 KB Output is correct
20 Correct 101 ms 17820 KB Output is correct
21 Correct 118 ms 18192 KB Output is correct
22 Correct 97 ms 18176 KB Output is correct
23 Correct 145 ms 18348 KB Output is correct
24 Correct 132 ms 18320 KB Output is correct
25 Correct 122 ms 17876 KB Output is correct

Subtask #5
0 / 18.0

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