Submission #1127103

#TimeUsernameProblemLanguageResultExecution timeMemory
1127103neverspotRace (IOI11_race)C++20
100 / 100
833 ms58992 KiB
/* "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 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) const { return dist[x] + dist[y] - 2 * dist[lca(x, y)]; } bool is_ancestor(int par, int child) const { return (start[par] <= start[child] && end[child] <= end[par]); } }; class CTree { public: int n = 0; int root = -1; vector<vector<pair<int,int>>> e, g; vi subtree_size; vb is_removed; int ans=INT_MAX; int k; 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,int w=1) { e[u].push_back({v,w}); e[v].push_back({u,w}); } int get_subtree_size(int node, int parent = -1) { subtree_size[node] = 1; for (auto& child : e[node] | views::keys) { 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 (auto& child : e[node] | views::keys) { 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,mii &data,bool filling,int depth=0,int dis=0) { if (filling) { if (data.contains(dis)) { data[dis]=min(static_cast<int>(data[dis]),depth); }else { data[dis]=depth; } }else { int want=k-dis; if (data.contains(want)) { ans=min(ans,static_cast<int>(data[want])+depth); } } for (auto &[child,w] : e[v]) { if (is_removed[child] || child==p) { continue; } cal(child,v,data,filling,depth+1,dis+w); } } void build(int node = 1,int p = -1) { int centroid = get_centroid(node, get_subtree_size(node)); is_removed[centroid] = true; mii data; data[0]=0; for (auto &[child,w] : e[centroid]) { if (is_removed[child] || child==p) { continue; } cal(child, centroid, data, false,1,w); cal(child, centroid, data, true,1,w); } for (auto child : e[centroid] | views::keys) { if (is_removed[child]) { continue; } build(child, centroid); } } }; int best_path(int n, int k, int edges[][2], int weights[]) { if (k == 1) { return 0; } ci n>>k; CTree ct(n); fl(0,n-1) { auto &[x,y]=edges[i]; int w=weights[i]; ct.addEdge(x,y,w); } ct.k=k; ct.build(); int ans=ct.ans; if (ans==INT_MAX)ans=-1; return ans; } // int main() { // int n, k; // ci n>>k; // int edges[n][2], weights[n]; // fl(0,n-1) { // int u, v, w; // ci u>>v>>w; // edges[i][0]=u, edges[i][1]=v; // weights[i]=w; // } // // cout<<best_path(n, k, edges, weights)<<endl; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...