Submission #795735

#	Time	Username	Problem	Language	Result	Execution time	Memory
795735		nnhzzz	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	671 ms	179168 KiB

mousetrap

// -------------------------Solution by Stormgamming------------------------- //
/* Author: Nguyen Ngoc Hung, Ngo Gia Tu high school */

/*
Tips:
    1.int? long long?
    2.don't submit wrong answer
    3.figure out logic first, then start writing please
    4.know about the range
    5.check if you have to input t or not
    6.modulo of negative numbers is not a%b, it is a%b + abs(b)
    7.special cases (n=1?)
*/

//-------------------------------------------------------------//
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <math.h>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <string>
#include <fstream>
#include <iterator>

using namespace std;

//-------------------------------------------------------------//
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O2")
#pragma GCC optimization ("O3")
*/

//-------------------------------------------------------------//
#define    SORT_UNIQUE(c)  (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define              vvvi  vector<vector<vector<int>>>
#define               vvi  vector<vector<int>>
#define                vi  vector<int>
#define               pii  pair<int,int>
#define               inf  0x3f3f3f3f
#define               pii  pair<int,int>
#define              endl  "\n"
#define           mask(i)  (1ll<<i)
#define            all(x)  (x).begin(),(x).end()
#define           rall(x)  (x).rbegin(),(x).rend()
#define             sz(x)  (int)(x).size()
#define            uni(a)  ((a).erase(unique(all(a)),(a).end()))
#define                se  second
#define          DEBUG(X)  {auto _X=(X); cerr << "L" << __LINE__ << ": " << #X << " = " << (_X) << endl;}
#define   count_bit(mask)  __builtin_popcountll(mask)
#define      reset(x,val)  memset((x),(val),sizeof(x))
#define          bit(i,j)  ((i>>j)&1ll)
#define               ull  unsigned long long
#define                ll  long long
#define                ld  long double
// #define               int  long long
#define                fi  first
#define   __Storgamming__  signed main()
#define repdis(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     repd(i,be,en)  for(int i = (be); i>=(en); i--)
#define      rep(i,be,en)  for(int i = (be); i<=(en); i++)
#define        file(name)  if(fopen(name".inp", "r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}

//-------------------------------------------------------------//
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(ld x) {cerr << x;}
void __print(ull x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x?"true":"false");}

//-------------------------------------------------------------//
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<class T> inline T sqr(T x) {return x*x;};

//-------------------------------------------------------------//
bool mem2;
const int N = (int)1e6+1;
const int SIZE = (int)1e6+10;
const int maxn = (int)1e6+1;
const int MOD = (int)1e9+7;
// const int oo = (int)1e18+7;
const int base = (int)311;
const ld PI = (ld)3.1415926535897932384626433832795;

//-------------------------------------------------------------//
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
vi adj[maxn];
int par[maxn],son[maxn],sum[maxn],f[maxn];
bool ok[maxn];
int n,m,root;

void dfs(int u, int dad){
  par[u] = dad;
  son[u] = sz(adj[u]);
  if(u!=root){
    son[u]--;
  }
  int ma1 = 0,ma2 = 0;
  if(u!=root){
    sum[u] = sum[dad]+son[u]-1+(u==m);
  }
  for(auto v:adj[u]){
    if(v==dad){
      continue;
    }
    dfs(v,u);
    if(f[v]>ma1){
      ma2 = ma1;
      ma1 = f[v];
    }else{
      maxi(ma2,f[v]);
    }
  }
  f[u] = ma2+son[u];
}

bool check(int lim){
  int cnt = 1;
  for(int u = m; u!=root; u = par[u],cnt++){
    int val = 0;
    for(auto v:adj[u]){
      if(ok[v]==true || v==par[u] || f[v]+sum[u]<=lim){
        continue;
      }
      if(!cnt){
        return false;
      }
      val++;
      cnt--;
    }
    lim -= val;
  }
  return (bool)(lim>=0);
}

void solve(){
  cin >> n >> root >> m;
  if(root==m){
    cout << 0;
    return ;
  }
  rep(i,2,n){
    int u,v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(root,0);
  for(int i = m; i!=root; i = par[i]){
    ok[i] = true;
  }
  int l = 0,r = n<<1,res = r;
  while(l<=r){
    int mid = (l+r)>>1;
    if(check(mid)==true){
      r = mid-1;
      res = mid;
    }else{
      l = mid+1;
    }
  }
  cout << res;
}

bool mem1;

//-------------------------------------------------------------//
__Storgamming__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;

    while(test--){
        solve();
    }
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35