Submission #706156

#TimeUsernameProblemLanguageResultExecution timeMemory
706156bLICFactories (JOI14_factories)C++17
15 / 100
8026 ms155276 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define ft first #define sd second #define pb push_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double 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 ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; const int maxN = 5e5+5; const int maxK = 21; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);} ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;} void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 10; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3 ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;} ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return mod_add(arr[0], 0, b);} //for non prime b template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } struct Edge{ int v, w; bool operator==(Edge e){ return v==e.v; } }; int n, m; ll ans; ll mdinv[maxN]; ll dist(int a, int b); struct Centroid{ std::vector<std::vector<Edge>> adj; std::vector<int> parent, stree; long long INF = 1e9; vector<ll> nearest; Centroid(){} Centroid(std::vector<std::vector<Edge>>& _adj):adj(_adj){ parent.resize((int)_adj.size()); stree.resize((int)_adj.size()); nearest.assign((int)_adj.size(), INFLL); } void build(int node = 1, int par = -1){ int n = dfssize(node, par); int centroid = dfscentroid(node, par, n); parent[centroid] = par; auto tmp = adj[centroid]; adj[centroid].clear(); for (Edge y:tmp) { int x = y.v; Edge tmp = {centroid, -1}; adj[x].erase(find(all(adj[x]), tmp)); build(x, centroid); } } int dfssize(int node, int par){ stree[node] = 1; for (Edge y:adj[node]){ int x = y.v; if (x==par) continue; dfssize(x, node); stree[node] += stree[x]; } return stree[node]; } int dfscentroid(int node, int par, int n){ for (Edge y:adj[node]){ int x = y.v; if (x==par) continue; if (stree[x]>n/2) return dfscentroid(x, node, n); } return node; } void color(int node){ nearest[node] = 0; int temp = node; while(parent[node]!=-1){ node = parent[node]; nearest[node] = min(nearest[node], dist(temp, node)); } } void decolor(int node){ nearest[node] = INFLL; while(parent[node]!=-1){ node = parent[node]; if (nearest[node]==INFLL) break; nearest[node] = INFLL; } } ll getnearest(int node){ ll ret = nearest[node]; int temp = node; while(parent[node]!=-1){ node = parent[node]; ret = min(ret, dist(temp, node) + nearest[node]); } return ret; } }; vector<vector<Edge>> adj; int par[maxN][maxK]; int dep[maxN]; ll depth[maxN]; void dfs(int node, int p){ for (Edge y:adj[node]){ int x = y.v; if (x==p) continue; par[x][0] = node; dep[x] = dep[node] + 1; depth[x] = depth[node] + y.w; dfs(x, node); } } int kup(int node, int h){ for (int i = 0;i<maxK;i++){ if ((h>>i)&1) node = par[node][i]; } return node; } int lca(int x, int y){ if (dep[x]>dep[y]) swap(x, y); y = kup(y, dep[y]-dep[x]); if (x==y) return x; for (int i = maxK-1;i>=0;i--){ if (par[x][i]!=par[y][i]) x = par[x][i], y = par[y][i]; } return par[x][0]; } ll dist(int u, int v){ return depth[u]+depth[v]-2*depth[lca(u, v)]; } Centroid ctr; void Init(int N, int A[], int B[], int D[]){ n = N; adj.resize(n); for (int i = 0;i<n-1;i++){ int u = A[i], v = B[i], w = D[i]; adj[u].pb({v, w}); adj[v].pb({u, w}); } dfs(0, -1); for (int j = 1;j<maxK;j++){ for (int i = 0;i<n;i++) par[i][j] = par[par[i][j-1]][j-1]; } ctr = Centroid(adj); ctr.build(0, -1); } long long Query(int S, int X[], int T, int Y[]){ ll res = INFLL; for (int i = 0;i<S;i++) ctr.color(X[i]); for (int i = 0;i<T;i++) res = min(res, ctr.getnearest(Y[i])); for (int i = 0;i<S;i++) ctr.decolor(X[i]); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...