oj.uz

답안 #830767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830767 2023-08-19T10:14:40 Z tranxuanbach 통행료 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3024 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -