Submission #566628

#	Time	Username	Problem	Language	Result	Execution time	Memory
566628		PiejanVDC	Highway Tolls (IOI18_highway)	C++17	0 / 100	250 ms	262144 KiB

highway

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

long long ask(const std::vector<int> &w);
void answer(int s, int t);

int search(int n, int D) {
	vector<int>A(n,1);
	int l = 0, r = n-1;
	int ans = -1;
	while(l <= r) {
		//cout << l << " " << r << "\n";
		if(l == r) {
			return l;
		}
		bool T = (r - l == 1);
		int mid = (l+r)/2;
		for(int i = mid+1 ; i <= r ; i++)
			A[i] = 0;
		if(ask(A) != D) {
			ans = l;
			r = mid;
		} else {
			for(int i = l ; i <= mid ; i++)
				A[i] = 0;
			for(int i = mid+1 ; i <= r ; i++)
				A[i] = 1;
			l = mid+1;
		}
	}
	return ans;
}

const int mxN = (int)9e4 + 5;

map<pair<int,int>,int>mp;

vector<int>adj[mxN];

vector<int>edges;
vector<int>go;

set<int>nC;

void dfs(int u, int d, int e = -1) {
	if(d == 1) {
		for(auto z : adj[u]) if(z != e && !nC.count(z)) {
			edges.push_back(mp[{u,z}]);
			go.push_back(z);
		}
		return;
	}
	for(auto z : adj[u]) if(z != e) {
		dfs(z, d-1, u);
	}
}

bool delDFS(int u, int S, int e = -1) {
	if(u == S) {
		nC.insert(u);
		return 1;
	}
	bool ok = 0;
	for(auto z : adj[u]) if(z != e) {
		ok |= delDFS(z, S, u);
	}
	if(ok)
		nC.insert(u);
	return ok;
}

int C = 1;

void check() {
//	cout << "Check " << C++ << "\n";
}

int conSearch(int m, int dist) {
	const int n = (int)edges.size();
	vector<int>A(m,0);
	int l = 0, r = n-1;
	int ans = -1;
	while(l <= r) {
		if(l == r)
			return go[l];
		int mid = (l+r)/2;
		for(auto &z : A)
			z = 0;
		for(int i = 0 ; i <= mid ; i++)
			A[edges[i]] = 1;
		if(ask(A) != dist) {
			r = mid;
			ans = go[mid];
		} else l = mid+1;
	}
	return ans;
}

void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
	const int m = (int)u.size();
	
	for(int i = 0  ; i < m ; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	vector<int>A(m,0);

	for(int i = 0 ; i < m ; i++)
		mp[{u[i],v[i]}] = mp[{v[i],u[i]}] = i;

	int dist = ask(A) / a;
	int id = search(m, dist * a);
	int f = u[id], s = v[id];
	int l = 0, r = dist;

	check();
//	cout << f << " " << s << "\n";

	int S,T;
	int D;

	while(l <= r) {
		edges.clear();
		go.clear();
		int mid = (l+r)/2;
		dfs(f,mid);

		for(auto &z : A)
			z = 0;

		for(auto z : edges)
			A[z] = 1;

		check();
		/*cout << l << " " << r << "\n";
		for(auto z : edges)
			cout << z << " ";
		cout << "\n";
*/
		if(ask(A) != dist*a) {
			S = conSearch(m, dist*a);
			l = mid+1;
			D = mid;
		} else r = mid-1;
		//cout << "S " << S << "\n";
	}

	if(S == -1)
		S = f;
	
	delDFS(f, S);

	check();
	/*for(auto it = nC.begin() ; it != nC.end() ; it++)
		cout << *it << " ";
	cout << "\n";
	*/

	edges.clear();
	go.clear();
	dfs(s, dist - D + 1);

	/*cout << "Final ";
	for(auto z : edges)
		cout << z << " ";
	cout << "\n";
*/
	T = conSearch(m, dist*a);

	check();
	//cout << S << " " << T << "\n";

	answer(S,T);
}


/*
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>

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;
}


*/

Compilation message (stderr)

highway.cpp: In function 'int search(int, int)':
highway.cpp:17:8: warning: unused variable 'T' [-Wunused-variable]
   17 |   bool T = (r - l == 1);
      |        ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:163:14: warning: 'D' may be used uninitialized in this function [-Wmaybe-uninitialized]
  163 |  dfs(s, dist - D + 1);
      |         ~~~~~^~~
highway.cpp:150:2: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
  150 |  if(S == -1)
      |  ^~

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