Submission #140420

#	Time	Username	Problem	Language	Result	Execution time	Memory
140420		arthurconmy	Highway Tolls (IOI18_highway)	C++14	0 / 100	24 ms	4388 KiB

highway

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

using namespace std;

using ll = long long;

int n;
const int MAXN=90000;
int cur_tree_size;

int sz[MAXN]; // subtree size
bool exists[MAXN];
vector<pair<int,int>> adj[MAXN];
bool c_vis[MAXN];
bool mark_vis[MAXN];
bool mark_one=0;
int c;
ll first_ask;
ll second_ask;
bool using_subtree[MAXN];

vector<pair<int,int>> candid_a; // the candidates <vertex,relevant_edge>
vector<pair<int,int>> candid_b;

bool final_vis[MAXN];
int a_dis[MAXN];
int b_dis[MAXN];

vector<int> ask_one(MAXN-1);
vector<int> ask_two(MAXN-1);

int the_a_dis;
int the_b_dis;

#ifdef ARTHUR_LOCAL
  int ans_index=0;
  vector<int> answers;

	ll ask(vector<int> V)
	{
		for(auto v:V) cout << v << " ";
    cout << endl;

    return answers[ans_index++];
	}

  void answer(int a, int b)
  {

    cout <<"YEAHHH" << a << " " << b << endl;
  }
#endif

void sz_dfs(int v)
{
	sz[v]++;

	for(auto u:adj[v])
	{
		if(sz[u.first]!=0 || !exists[u.first]) continue; // does this make the code work
		
		sz_dfs(u.first);
		sz[v]+=sz[u.first];
	}
}

int c_dfs(int v)
{
	c_vis[v]=1;

	for(auto u:adj[v])
	{
		if(c_vis[u.first] || !exists[u.first]) continue;

		if(sz[u.first] > int(cur_tree_size/2)) return c_dfs(u.first);
	}

	return v;
}

void mark_dfs(int v)
{
	mark_vis[v]=1;

	for(auto u:adj[v])
	{
		if(mark_vis[u.first] || !exists[u.first]) continue;

		if(mark_one) ask_one[u.second]=1;
		else ask_two[u.second]=1;
	}
}

void exist_dfs(int v)
{
	exists[v]=0;

	for(auto u:adj[v])
	{
		if(!exists[u.first] || u.first==c) continue;

		exist_dfs(u.first);
	}
}

void a_dfs(int v)
{
  final_vis[v]=1;

  for(auto u:adj[v])
  {
    if(final_vis[u.first] || !exists[u.first]) continue;
    a_dis[u.first]=a_dis[v]+1;
    if(a_dis[u.first] == the_a_dis) candid_a.push_back(make_pair(u.first,u.second));

    a_dfs(u.first);
  }
}

void b_dfs(int v)
{
  final_vis[v]=1;

  for(auto u:adj[v])
  {
    if(final_vis[u.first] || !exists[u.first]) continue;
    b_dis[u.first]=b_dis[v]+1;
    if(b_dis[u.first] == the_b_dis) candid_b.push_back(make_pair(u.first,u.second));

    b_dfs(u.first);
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	// initialise things

	n=N;

	for(int i=0; i<n-1; i++)
	{
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}

	for(int i=0; i<n; i++) exists[i]=1;

	// okay now figure out the 'base distance'

	vector<int> base_w(n-1); // should be initialised with all zeroes

	ll path_length = ask(base_w);

	// do some more initialisation ... 

	cur_tree_size=n;
	int root=-1;
	c=0;

	while(true) // continually discards >= 1/4 of the current graph
	{
		for(int i=0; i<n; i++)
		{
			sz[i]=0;
			c_vis[i]=0;
		}

		sz_dfs(c);
		c = c_dfs(c);

		//cout << "CENTROID: " << c << endl;

//		cout << "SIZES" << endl;

	//	for(int i=0; i<n; i++) cout << sz[i] << " ";
		//cout << endl;

		vector<pair<int,int>> subtrees;

		for(auto u:adj[c])
		{
			if(sz[u.first]>sz[c])
      {
        subtrees.push_back({cur_tree_size-sz[c],u.first});
			//  cout << u.first << " has a subtree of size " << cur_tree_size-sz[c] << endl;
      }
      else
      {
        //cout << u.first << " has a subtree of size " << sz[u.first] << endl;
        subtrees.push_back({sz[u.first],u.first});
      }
		}

		sort(subtrees.rbegin(),subtrees.rend()); // so the largest subtrees are first
	
		vector<int> subtrees_used;
		// vector<bool> using_subtree(MAXN);

    for(int i=0; i<n; i++) using_subtree[i]=0;

		int cur_subtree_total_size=1;

		for(auto u:subtrees)
		{
			if(cur_subtree_total_size > int(cur_tree_size/4)) break; // this is causing problems because in really small trees (size < 4)

			cur_subtree_total_size += u.first;

			subtrees_used.push_back(u.second);
			using_subtree[u.second]=1;

			//cout << u.first << " " << u.second << "are being used" << endl;
		}

		for(int i=0; i<n-1; i++)
		{
			ask_one[i]=0;
			ask_two[i]=0;
			mark_vis[i]=0;
			mark_vis[i+1]=0;
		}

		for(auto u:adj[c])
		{
			if(!exists[u.first]) continue;

			if(using_subtree[u.first]) ask_one[u.second]=1;
			else ask_two[u.second]=1; // I think that this is correct
		
			mark_one = using_subtree[u.first];

			mark_dfs(u.first);
		}

		//for(int i=0; i<n-1; i++) cout << ask_one[i] << " ";
		//cout << endl;
		//for(int i=0; i<n-1; i++) cout << ask_two[i] << " ";
		//cout << endl;

    vector<int> real_ask_one;
    vector<int> real_ask_two;

    for(int i=0; i<n-1; i++)
    {
      real_ask_one.push_back(ask_one[i]);
      real_ask_two.push_back(ask_two[i]);
    }

		first_ask = ask(real_ask_one);
		second_ask = ask(real_ask_two);

		// okay so now we have a vertex which we know the
		// path passes through, and the division of which 
		// vertices exiting it are on which side

		if(min(first_ask,second_ask) > path_length) 
		{
			root=c;
			break;
		}

		for(auto u:adj[c])
		{
			if(using_subtree[u.first])
			{
				//cout << u.first << endl;

				if(first_ask==path_length) exist_dfs(u.first);
			}

			else
			{
				if(second_ask==path_length) exist_dfs(u.first);
			}
		}

		//cout << "ASKS" << endl;
		//cout << first_ask << " " << second_ask << " " << path_length << endl;

		//cout << "EXISTENT" << endl;
		//for(int i=0; i<n; i++) cout << exists[i] << " ";
		//cout << endl;

		cur_tree_size=0;
		for(int i=0; i<n; i++)
		{
			if(exists[i]) cur_tree_size++;
		}

    if(cur_tree_size<4) break;
	}

  // okay so now we have the two cases: the 'root' and the tree size < 4

  if(root!=-1)
  {
    the_a_dis = ll((first_ask - path_length)/ll(B-A));
    the_b_dis = ll((second_ask - path_length)/ll(B-A));

    for(auto u:adj[c])
    {
      if(!exists[u.first]) continue;

      if(using_subtree[u.first]) a_dfs(u.first);
      else b_dfs(u.first);
    }

    // uhhh ... now we need to do the two 'binary searches'

    int pass=candid_a.size()-1;
    int fail=-1;

    while(pass-fail>1)
    {
      int mid = (pass+fail)/2;

      vector<int> askin(n-1);

      for(int i=0; i<=mid; i++)
      {
        askin[candid_a[i].second]=1;
      }

      int cur_ans = ask(askin);

      if(cur_ans == path_length)
      {
        fail = mid;
      }

      else
      {
        pass = mid;
      }
    }

    int first_part = pass;

    pass=candid_b.size()-1;
    fail=-1;

    while(pass-fail>1)
    {
      int mid = (pass+fail)/2;

      vector<int> askin(n-1);

      for(int i=0; i<=mid; i++)
      {
        askin[candid_b[i].second]=1;
      }

      int cur_ans = ask(askin);

      if(cur_ans == path_length)
      {
        fail = mid;
      }

      else
      {
        pass = mid;
      }
    }

    answer(first_part,pass);
    return;
  }

  else
  {
    // brute force all possibilities on the 2/3 vertex graph

    vector<int> vert;

    for(int i=0; i<n; i++)
    {
      if(exists[i]) vert.push_back(i);
    }

    //cout << vert.size() << endl;

    if(vert.size()==2)
    {
      answer(vert[0],vert[1]);
      return;
    }

    int middle;
    int adj_guy=-1;
    int deg=0;

    for(auto u:adj[vert[0]])
    {
      if(u.first == vert[1] || u.first == vert[2])
      {
        adj_guy=u.first;
        deg++;
      }
    }

    if(deg==2) middle=vert[0];
    else middle = adj_guy;

    //cout << middle << endl;

    int side1=-1;
    int side2=-1;

    for(auto u:vert)
    {
      // cout << u <<"!"<<endl;
      if(u!=middle && side1==-1) side1=u;
      else
      {
        if(u!=middle) side2=u;
      }
    }

    int edge1=-1;
    int edge2=-1;

    for(auto u:adj[middle])
    {
      if(u.first==side1) edge1=u.second;
      if(u.first==side2) edge2=u.second;
    }

    // cout << edge1 << " " << edge2 << endl;

    vector<int> askin(n-1);

    askin[edge1]=1;
    askin[edge2]=1;

    if(ask(askin) == ll(B+B))
    {
      answer(side1,side2);
      return;
    }

    askin[edge2]=0;

    if(ask(askin) == ll(B))
    {
      answer(middle,side1);
      return;
    }

    answer(middle,side2);
    return;
  }

/*  int M = U.size();
  for (int j = 0; j < 50; ++j) {
    std::vector<int> w(M);
    for (int i = 0; i < M; ++i) {
      w[i] = 0;
    }
    long long toll = ask(w);
  }
  answer(0, N - 1);*/
}

#ifdef ARTHUR_LOCAL
	int main()
	{
    answers={1,1,2};
		find_pair(2,{0},{1},1,2);
	}
#endif

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