Submission #1127094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127094		neverspot	Race (IOI11_race)	C++20	0 / 100	1 ms	328 KiB

race

/* "If I can run I will run , If I can walk I will walk , If I can crawl I will crawl" */
/*                           " But I will NEVER_STOP "                                 */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
using namespace std;
using namespace __gnu_pbds;
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define NeverSpot cout.tie(NULL);
// #define int long long
#define double long double
#define f first
#define s second
#define ed <<endl;
#define co cout<<
#define ci cin>>
#define sped <<" ";
#define sp <<" "<<
#define love cout<<" Insha " ed
#define all(x) (x).begin(),(x).end()
#define fl(a,b) for (int i=a;i<(b);++i)
#define rfl(a,b) for (int i=a;i>=(b);--i)
#define sl(a,b) for (int j=a;j<(b);++j)
#define rsl(a,b) for (int j=a;j>=(b);--j)
#define tl(a,b) for (int k=a;k<(b);++k)
#define rtl(a,b) for (int k=a;k>=(b);--k)
#define test(t) int t;cin>>t;for(int O=1;O<=t;O++)
#define sortv(v) sort(all(v));
#define sumv(arr) accumulate(all(arr),0LL)
#define rev(v) reverse(all(v));
#define ai(o,size) vi o;fl(0,size){int p ; cin>>p ; (o).push_back(p);}
#define Mod 1000000007ll
#define Emod 998244353ll
#define inf 1000000000000000009ll
#define gcd __gcd
inline int Sqrt(int x){ int y=static_cast<long long>(sqrt(x))+5;while(y*y>x)y--;return y;}
#define log2(x) (64 - __builtin_clzll(x) - 1) // log2 in O(1) time
using mii = map<long long, long long>;
using vi = vector<long long>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<long long>>;
using vvp = vector<vector<pair<long long, long long>>>;
using pii = pair<long long, long long>;
using vp = vector<pair<long long, long long>>;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_set; // find_by_order, order_of_key
typedef tree<pair<int,int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_multiset; // find_by_order, order_of_key
string al="abcdefghijklmnopqrstuvwxyz";

//.........For Taking Mod............//
inline int power(int a, int b, int mod=Mod) {int res = 1; while (b > 0) {if (b & 1)res = res * a % mod; a = a * a % mod; b = b >> 1;} return res;}
class mod
{
   static int mminvprime(int a, int b) {return power(a, b - 2, b);}
public:
   int m=Mod;
   void set(int m) {this->m=m;}
   int add(int a, int b) {a = a % m; b = b % m; return ((a + b) % m + m) % m;}
   int mul(int a, int b) {a = a % m; b = b % m; return (a * b % m + m) % m;}
   int sub(int a, int b) {a = a % m; b = b % m; return ((a - b) % m + m) % m;}
   int div(int a, int b) {a = a % m; b = b % m; return (mul(a, mminvprime(b, m)) + m) % m;}  //only for prime m
}mod;

//.........Bit_Manipulation...........//
#define msb(mask) (63-__builtin_clzll(mask))  /// 0 -> -1
#define lsb(mask) __builtin_ctzll(mask)  /// 0 -> 64
#define cntsetbit(mask) __builtin_popcountll(mask)
#define checkbit(mask,bit) ((mask >> bit) & 1ll)
#define onbit(mask,bit) ((mask)|(1LL<<(bit)))
#define offbit(mask,bit) ((mask)&~(1LL<<(bit)))
#define changebit(mask,bit) ((mask)^(1LL<<bit))

// random number generator #BESTEST_QUAILTY :)
// mt19937_64 gen(random_device{}());
// long long rng(int l=0,int r=INT64_MAX){uniform_int_distribution dist(l, r);return dist(gen);}
//
// // Custom hashing for unordered map or set
// const int RANDOM = rng();
// struct chash{int operator()(int x) const { return x ^ RANDOM; }};

// Function
#define Ceil(a,b) ((a+b-1)/b)
#define print(arr) for(auto &o:(arr)){co o sped;} cout ed
#define mxe(v)  *max_element(v.begin(),v.end())     // find max element in vector
#define mne(v)  *min_element(v.begin(),v.end())     // find min element in vector
inline bool isPrime(int v) {if(v==1) return false; if(v <= 3)return true;if ( v % 2 == 0 || v % 3 == 0)return false;int i = 5;while (i * i <= v) {if (v % i == 0 || v % (i + 2) == 0)return false;i += 6;}return true;}
inline void printbin(int v,int upto=10) {cout<<v<<"-> ";for (int i = upto; i >= 0; --i) {cout<<checkbit(v,i) sped}cout ed}
bool isEqual(double a, double b, double epsilon = 1e-9) {return abs(a - b) <= epsilon * (1ll + max(abs(a), abs(b)));}
inline bool limit_check(long long a, long long b, int max_bits = 59) {if (a == 0 || b == 0) return true;return msb(a) + msb(b) >= 128 - max_bits;}
namespace std {
   // fast swap
   void swap(order_set &a, order_set &b) { a.swap(b); }
   void swap(order_multiset &a, order_multiset &b) { a.swap(b); }
}

// Free to use :}


class CTree {
public:
   int n = 0;
   int root = -1;
   vector<vector<int>> e, g;
   vi subtree_size;
   vb is_removed;


   CTree(int n) : n(n), e(n + 1), g(n + 1), subtree_size(n + 1, 0), is_removed(n + 1, false) {}


   void addEdge(int u, int v) {
      e[u].push_back(v);
      e[v].push_back(u);
   }

   int get_subtree_size(int node, int parent = -1) {
      subtree_size[node] = 1;
      for (int child : e[node]) {
         if (child == parent || is_removed[child]) {
            continue;
         }
         subtree_size[node] += get_subtree_size(child, node);
      }
      return subtree_size[node];
   }

   int get_centroid(int node, int tree_size, int parent = -1) {
      for (int child : e[node]) {
         if (child == parent || is_removed[child]) {
            continue;
         }
         if (subtree_size[child] * 2 > tree_size) {
            return get_centroid(child, tree_size, node);
         }
      }
      return node;
   }

   void cal(int v,int p,int depth=1) {

      for (int child : e[v]) {
         if (is_removed[child] || child==p) { continue; }
         cal(child,v,depth+1);
      }

   }
   void build(int node = 1,int p = -1) {
      int centroid = get_centroid(node, get_subtree_size(node));
      is_removed[centroid] = true;


      if (root == -1)root = centroid;
      if (p != -1) {
         g[p].push_back(centroid);
         g[centroid].push_back(p);
      }

      for (int child : e[centroid]) {
         if (is_removed[child]) {
            continue;
         }
         build(child, centroid);
      }
   }
};


class Tree {
public:
   int n;
   vector<vector<pair<int,int>>> e;
   vector<vector<int>> lift;
   vector<int> start, end, dist, par,depth;
   bool Build = false, initialized = false;
   int timer = 0;

   Tree(int n) : n(n), e(n + 1),depth(n+1), lift(n + 1, vector<int>(20, -1)),
                 start(n + 1), end(n + 1), dist(n + 1, 0), par(n + 1) {
      initialized = true;
   }

   void addEdge(int u, int v,int w=1) {
      if (!initialized) {
         co "Tree not initialized" ed;
         exit(0);
      }
      e[u].emplace_back(v,w);
      e[v].emplace_back(u,w);
   }

   void parentOf(int v, int p,int w=1) {
      e[v].emplace_back(p,w);
      e[p].emplace_back(v,w);
   }

   void build(int root = 1) {
      dfs(root, root);
      Build = true;
      for (int step = 1; step < 20; step++) {
         for (int i = 1; i <= n; i++) {
            if (lift[i][step - 1] != -1)
               lift[i][step] = lift[lift[i][step - 1]][step - 1];
         }
      }
   }

   void dfs(int v, int p) {
      par[v] = p;
      start[v] = timer++;
      for (auto [child,w] : e[v]) {
         if (child == p) continue;
         dist[child] = dist[v] + w;
         depth[child] = depth[v] + 1;
         lift[child][0] = v;
         dfs(child, v);
      }
      end[v] = timer;
   }


   int up(int node, int step) const {
      if (!Build) {
         co "Build must be called before using `up`" ed;
         exit(0);
      }
      fl(0, 20) {
         if (checkbit(step, i) && node != -1)
            node = lift[node][i];
      }
      return node;
   }

   int lca(int a, int b) const {
      if (!Build) {
         co "Build must be called before using `lca`" ed;
         exit(0);
      }
      if (is_ancestor(a, b)) return a;
      if (is_ancestor(b, a)) return b;

      int maxStep = log2(n);
      for (int step = maxStep; step >= 0; step--) {
         if (lift[a][step] != -1 && !is_ancestor(lift[a][step], b)) {
            a = lift[a][step];
         }
      }
      return lift[a][0];
   }

   int distance(const int x, const int y,vector<int> &d) {
      return d[x] + d[y] - 2 * d[lca(x, y)];
   }

   bool is_ancestor(int par, int child) const {
      return (start[par] <= start[child] && end[child] <= end[par]);
   }
};


int best_path(int n, int k, int edges[][2], int weights[]) {
   if (k == 1) { return 0; }

   ci n>>k;
   CTree ct(n);
   Tree t(n);

   fl(0,n-1) {
      auto &[x,y]=edges[i];
      int w=weights[i];
      t.addEdge(x,y,w);
      ct.addEdge(x,y);
   }
   ct.build();
   t.build();




   int ans=INT_MAX;
   function<void(int, int)> dfs = [&](int v, int p) {


      mii cnt;
      cnt[t.dist[v]]=t.depth[v];
      function<void(int, int,int,bool)> cal = [&](int v, int p,int root,bool filling) {

         int edgeCnt=t.distance(v,root,t.depth);
         int dis=t.distance(v,root,t.dist);
         if (filling) {
            if (cnt.contains(dis)) {
               int f=cnt[dis];
               cnt[dis]=min(f,edgeCnt);
            }else {
               cnt[dis]=edgeCnt;
            }
         }else {
            int want=k-dis;
            if (cnt.contains(want)) {
               int f=cnt[want]+edgeCnt;
               ans = min(ans,f);
            }
         }

         for (auto child : ct.g[v]) {
            if (child == p)continue;

            cal(child, v,root,filling);
         }
      };

      for (auto child : ct.g[v]) {
         if (child == p)continue;

         dfs(child, v);
         cal(child, v, v,false);
         cal(child, v, v,true);
      }
   };
   dfs(ct.root,-1);
   if (ans==INT_MAX)ans=-1;
   return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57