oj.uz

Submission #795735

# Submission time Handle Problem Language Result Execution time Memory
795735 2023-07-27T13:49:58 Z nnhzzz Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 671 ms 179168 KB 
// -------------------------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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23744 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23780 KB Output is correct
4 Correct 11 ms 23816 KB Output is correct
5 Correct 12 ms 23792 KB Output is correct
6 Correct 12 ms 23744 KB Output is correct
7 Correct 12 ms 23828 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 84096 KB Output is correct
2 Correct 210 ms 78020 KB Output is correct
3 Correct 671 ms 85072 KB Output is correct
4 Correct 309 ms 54292 KB Output is correct
5 Correct 656 ms 85104 KB Output is correct
6 Correct 603 ms 85072 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23744 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23780 KB Output is correct
4 Correct 11 ms 23816 KB Output is correct
5 Correct 12 ms 23792 KB Output is correct
6 Correct 12 ms 23744 KB Output is correct
7 Correct 12 ms 23828 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23816 KB Output is correct
13 Correct 14 ms 23812 KB Output is correct
14 Correct 12 ms 23968 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23828 KB Output is correct
17 Correct 12 ms 23848 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 15 ms 23864 KB Output is correct
21 Correct 13 ms 23864 KB Output is correct
22 Correct 12 ms 23856 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23744 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23780 KB Output is correct
4 Correct 11 ms 23816 KB Output is correct
5 Correct 12 ms 23792 KB Output is correct
6 Correct 12 ms 23744 KB Output is correct
7 Correct 12 ms 23828 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 233 ms 84096 KB Output is correct
12 Correct 210 ms 78020 KB Output is correct
13 Correct 671 ms 85072 KB Output is correct
14 Correct 309 ms 54292 KB Output is correct
15 Correct 656 ms 85104 KB Output is correct
16 Correct 603 ms 85072 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23816 KB Output is correct
19 Correct 14 ms 23812 KB Output is correct
20 Correct 12 ms 23968 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 12 ms 23828 KB Output is correct
23 Correct 12 ms 23848 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23892 KB Output is correct
26 Correct 15 ms 23864 KB Output is correct
27 Correct 13 ms 23864 KB Output is correct
28 Correct 12 ms 23856 KB Output is correct
29 Correct 12 ms 23764 KB Output is correct
30 Correct 244 ms 84140 KB Output is correct
31 Correct 226 ms 84156 KB Output is correct
32 Correct 372 ms 179168 KB Output is correct
33 Correct 268 ms 178136 KB Output is correct
34 Correct 609 ms 85072 KB Output is correct
35 Correct 617 ms 85196 KB Output is correct
36 Correct 634 ms 94412 KB Output is correct
37 Correct 646 ms 94496 KB Output is correct
38 Correct 555 ms 97328 KB Output is correct
39 Correct 457 ms 97244 KB Output is correct
40 Correct 463 ms 97252 KB Output is correct