Submission #990761

#	Time	Username	Problem	Language	Result	Execution time	Memory
990761		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	155 ms	36048 KiB

torrent

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5;
vector<int> G[N], child[N];
vector<int> pth;
bool dead[N];
int mx[N], cnt[N], mi[N];

bool sorter(int a, int b)
{
  return mx[a] < mx[b];
}

void path(int s, int d, int p = 0)
{
  pth.push_back(s);

  for(int u : G[s])
    if(u != p && pth.back() != d)
      path(u, d, s);

  if(pth.back() != d)
    pth.pop_back();
}

void dfs_child(int v, int p = 0)
{
  for(int u : G[v])
    if(!dead[u] && p != u)
      {
	child[v].push_back(u);
	dfs_child(u, v);
      }
}

void dfs_dp(int v)
{
  // cerr << v << ' ';
  for(int c : child[v])
    dfs_dp(c);

  sort(child[v].rbegin(), child[v].rend(), sorter);
  vector<int> vec;
  int i = 1;
  for(int c : child[v])
    vec.push_back(mx[c] + i), i++;

  if(vec.empty())
    {
      mx[v] = mi[v] = cnt[v] = 0;
      return;
    }
  
  sort(vec.begin(), vec.end());
  // cerr << "V = " << v << endl;
  mx[v] = vec.back();
  mi[v] = vec.front();
  for(int i : vec)
    cnt[v] += (i == vec.back());
}

int main()
{
  int n, a, b;
  cin >> n >> a >> b;
  for(int i = 1; i < n; i ++)
    {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }

  path(a, b);
  for(int v : pth)
    dead[v] = true;

  for(int v : pth)
    dfs_child(v);
  
  for(int v : pth)
    {
      //cerr << "Tree : ";
      dfs_dp(v);
      //cerr << endl;
      // cerr << "mx[" << v << "] = " << mx[v] << endl;
      // cerr << "cnt[" << v << "] = " << cnt[v] << endl;
    }
  // for(int v : pth)
  //  cout << v << ' ' << cnt[v] << '\n';
  
  int l = -1, r = n + 1;
  while(r - l > 1)
    {
      int t = (l + r) / 2;
      bool can = true;

      // for(int v : pth)
      //	cout << cnt[v] << ' ';
      //cout << endl;
       
      int tm[pth.size()];
      int add = 0, i = 0;
      for(int v : pth)
	{
	  if(add + mx[v] < t)
	    tm[i] = mx[v] + add + 1, add++;
	  else
	      tm[i] = mx[v] + add, add += cnt[v];
	  i++;
	}
      add = 0;
      for(i = pth.size() - 1; i >= 0; i--)
	{
	  int v = pth[i];
	  // cerr << add << ' ' << v << endl;
	  if(add + mx[v] < t)
	    tm[i] = min(tm[i], mx[v] + add + 1), add += 1;
	  else
	    tm[i] = min(tm[i], mx[v] + add), add += cnt[v];
	}
      for(int i = 0; i < pth.size(); i++)
	if(tm[i] > t)
	  can = false;

      if(can)
	r = t;
      else
	l = t;
    }
  cout << r << endl; 
  
  return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:124:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |       for(int i = 0; i < pth.size(); i++)
      |                      ~~^~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69