oj.uz

Submission #830767

# Submission time Handle Problem Language Result Execution time Memory
830767 2023-08-19T10:14:40 Z tranxuanbach Highway Tolls (IOI18_highway) C++17
12 / 100
 124 ms 10784 KB 
#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

using ll = long long;

struct edge_t{
	int u, v;
};

const int N = 90'000 + 5, M = 130'000 + 5;

int n, m;
vector <edge_t> edge;
vector <int> adj[N];

vector <int> vquery;

namespace subtask12{
	bool check(){
		return m == n - 1;
	}

	int pv[N];
	int pe[N];
	int ctrtour, tour[N];

	void dfs_tour(int u){
		tour[ctrtour] = u;
		ctrtour++;
		for (auto i: adj[u]){
			auto v = u ^ edge[i].u ^ edge[i].v;
			if (v == pv[u]){
				continue;
			}
			pv[v] = u;
			pe[v] = i;
			dfs_tour(v);
		}
	}

	int solve_fixed(int s){
		pv[s] = -1;
		pe[s] = -1;
		ctrtour = 0;
		dfs_tour(s);

		fill(vquery.begin(), vquery.end(), 1);
		ll length_path = ask(vquery);

		int lo = 1, hi = n - 1;
		while (lo < hi){
			int mid = (lo + hi) >> 1;
			fill(vquery.begin(), vquery.end(), 0);
			for (int pos = 1; pos <= mid; pos++){
				vquery[pe[tour[pos]]] = 1;
			}
			if (ask(vquery) == length_path){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
		}
		return tour[lo];
	}

	void solve(){
		int s = 0;
		int t = solve_fixed(s);
		answer(s, t);
	}
}

void find_pair(int _n, vector <int> _u, vector <int> _v, int a, int b){
	n = _n;
	m = isz(_u);
	edge.resize(m);
	for (int i = 0; i < m; i++){
		int u = _u[i], v = _v[i];
		edge[i] = edge_t{u, v};
		adj[u].emplace_back(i);
		adj[v].emplace_back(i);
	}
	vquery.resize(m);

	if (subtask12::check()){
		subtask12::solve();
		return;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2432 KB Output is correct
4 Correct 1 ms 2336 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2432 KB Output is correct
8 Correct 1 ms 2420 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 1 ms 2384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 10 ms 3184 KB Output is correct
3 Correct 87 ms 8864 KB Output is correct
4 Correct 97 ms 8908 KB Output is correct
5 Correct 82 ms 8864 KB Output is correct
6 Correct 102 ms 8860 KB Output is correct
7 Correct 95 ms 8868 KB Output is correct
8 Correct 67 ms 8860 KB Output is correct
9 Correct 124 ms 8876 KB Output is correct
10 Correct 114 ms 8868 KB Output is correct
11 Correct 76 ms 10120 KB Output is correct
12 Correct 81 ms 10784 KB Output is correct
13 Correct 87 ms 10232 KB Output is correct
14 Correct 67 ms 9696 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3664 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 1 ms 2384 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 9 ms 2924 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3024 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -