제출 #785893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785893		esomer	통행료 (IOI18_highway)	C++17	51 / 100	131 ms	21096 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"

using namespace std;

typedef long long ll;

//~ ll ask(vector<int> w);
//~ void answer(int s, int t);

void DFS(int x, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& pr, vector<vector<int>>& depth, int p, int edge, int d){
	pr[x] = {p, edge};
	depth[d].push_back(x);
	for(pair<int, int> pr2 : adj[x]){
		int node = pr2.first;
		int e = pr2.second;
		if(node != p) DFS(node, adj, pr, depth, x, e, d + 1);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	int n = N;
	int m = (int)U.size();
	if(m != n - 1) {answer(0, 1); return;}
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++){
		int a = U[i]; int b = V[i];
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
	}
	vector<pair<int, int>> p(n);
	vector<vector<int>> depth(n);
	DFS(0, adj, p, depth, -1, -1, 0);
	vector<int> w(m, 0);
	ll dist = ask(w) / A;
	//Now I want to find the depth of the lowest node in the tree.
	int lo = 0;
	int hi = n-1;
	int bst;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		w.assign(m, 0);
		for(int i = 0; i <= mid; i++){
			for(int x : depth[i]){
				if(x == 0) continue;
				w[p[x].second] = 1;
			}
		}
		ll d = ask(w);
		if(d == dist * B){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	lo = 0;
	hi = (int)depth[bst].size() - 1;
	int s;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		w.assign(m, 0);
		for(int i = lo; i <= mid; i++){
			int x = depth[bst][i];
			if(x == 0) continue;
			w[p[x].second] = 1;
		}
		ll d = ask(w);
		if(d != dist * A){
			s = depth[bst][mid];
			hi = mid - 1;
		}else lo = mid + 1;
	}
	w.assign(m, 0);
	int curr_node = s;
	while(p[curr_node].second != -1){
		w[p[curr_node].second] = 1;
		curr_node = p[curr_node].first;
	}
	ll dist2 = ask(w);
	ll depth_anc = bst - ((dist2 - dist * A) / (B-A));
	ll bst2 = dist - bst + 2 * depth_anc;
	if(bst - bst2 == dist){
		int curr_node = s;
		int curr_depth = bst;
		while(curr_node != -1){
			if(curr_depth == bst2){
				answer(s, curr_node); return;
			}
			curr_node = p[curr_node].first;
			curr_depth--;
		}
	}
	lo = 0;
	hi = (int)depth[bst2].size() - 1;
	int t;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		vector<int> added;
		for(int i = lo; i <= mid; i++){
			int x = depth[bst2][i];
			if(x == 0 || w[p[x].second] == 1) continue;
			w[p[x].second] = 1;
			added.push_back(p[x].second);
		}
		ll d = ask(w);
		if(d != dist2){
			t = depth[bst2][mid];
			hi = mid - 1;
		}else lo = mid + 1;
		for(int x : added) w[x] = 0;
	}
	answer(s, t);
	return;
}

//~ namespace {

//~ constexpr int MAX_NUM_CALLS = 100;
//~ constexpr long long INF = 1LL << 61;

//~ int N, M, A, B, S, T;
//~ std::vector<int> U, V;
//~ std::vector<std::vector<std::pair<int, int>>> graph;

//~ bool answered, wrong_pair;
//~ int num_calls;

//~ int read_int() {
  //~ int x;
  //~ if (scanf("%d", &x) != 1) {
    //~ fprintf(stderr, "Error while reading input\n");
    //~ exit(1);
  //~ }
  //~ return x;
//~ }

//~ void wrong_answer(const char *MSG) {
  //~ printf("Wrong Answer: %s\n", MSG);
  //~ exit(0);
//~ }

//~ }  // namespace

//~ long long ask(const std::vector<int> &w) {
  //~ if (++num_calls > MAX_NUM_CALLS) {
    //~ wrong_answer("more than 100 calls to ask");
  //~ }
  //~ if (w.size() != (size_t)M) {
    //~ wrong_answer("w is invalid");
  //~ }
  //~ for (size_t i = 0; i < w.size(); ++i) {
    //~ if (!(w[i] == 0 || w[i] == 1)) {
      //~ wrong_answer("w is invalid");
    //~ }
  //~ }

  //~ std::vector<bool> visited(N, false);
  //~ std::vector<long long> current_dist(N, INF);
  //~ std::queue<int> qa, qb;
  //~ qa.push(S);
  //~ current_dist[S] = 0;
  //~ while (!qa.empty() || !qb.empty()) {
    //~ int v;
    //~ if (qb.empty() ||
        //~ (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      //~ v = qa.front();
      //~ qa.pop();
    //~ } else {
      //~ v = qb.front();
      //~ qb.pop();
    //~ }
    //~ if (visited[v]) {
      //~ continue;
    //~ }
    //~ visited[v] = true;
    //~ long long d = current_dist[v];
    //~ if (v == T) {
      //~ return d;
    //~ }
    //~ for (auto e : graph[v]) {
      //~ int vv = e.first;
      //~ int ei = e.second;
      //~ if (!visited[vv]) {
        //~ if (w[ei] == 0) {
          //~ if (current_dist[vv] > d + A) {
            //~ current_dist[vv] = d + A;
            //~ qa.push(vv);
          //~ }
        //~ } else {
          //~ if (current_dist[vv] > d + B) {
            //~ current_dist[vv] = d + B;
            //~ qb.push(vv);
          //~ }
        //~ }
      //~ }
    //~ }
  //~ }
  //~ return -1;
//~ }

//~ void answer(int s, int t) {
  //~ if (answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }

  //~ if (!((s == S && t == T) || (s == T && t == S))) {
    //~ wrong_pair = true;
  //~ }

  //~ answered = true;
//~ }

//~ int main() {
  //~ N = read_int();
  //~ M = read_int();
  //~ A = read_int();
  //~ B = read_int();
  //~ S = read_int();
  //~ T = read_int();
  //~ U.resize(M);
  //~ V.resize(M);
  //~ graph.assign(N, std::vector<std::pair<int, int>>());
  //~ for (int i = 0; i < M; ++i) {
    //~ U[i] = read_int();
    //~ V[i] = read_int();
    //~ graph[U[i]].push_back({V[i], i});
    //~ graph[V[i]].push_back({U[i], i});
  //~ }

  //~ answered = false;
  //~ wrong_pair = false;
  //~ num_calls = 0;
  //~ find_pair(N, U, V, A, B);
  //~ if (!answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }
  //~ if (wrong_pair) {
    //~ wrong_answer("{s, t} is wrong");
  //~ }
  //~ printf("Accepted: %d\n", num_calls);
  //~ return 0;
//~ }

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:111:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |  answer(s, t);
      |  ~~~~~~^~~~~~
highway.cpp:86:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     answer(s, curr_node); return;
      |     ~~~~~~^~~~~~~~~~~~~~
highway.cpp:56:21: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  hi = (int)depth[bst].size() - 1;
      |                     ^

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