제출 #414951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414951		SuhaibSawalha1	통행료 (IOI18_highway)	C++17	5 / 100	24 ms	1088 KiB

highway

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

vector<vector<array<int, 2>>> adj;
int n, m, dp, A, B;

void dfs (int u = 0, int p = -1, int d = 1) {
	for (auto &v : adj[u]) {
		if (v[0] ^ p) {
			if (d == dp) {
				vector<int> ak(m, 0);
				ak[v[1]] = 1;
				if (ask(ak) != d * 1LL * A) {
					answer(0, v[0]);
					return;
				}
			}	
			else {
				dfs(v[0], u, d + 1);
			}
		}
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	::A = A;
	::B = B;
	adj.assign(n, {});
	for (int i = 0; i < m; ++i) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}	
	dp = ask(vector<int>(m, 0)) / A;
	dfs();
}	

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31