Submission #706214

#TimeUsernameProblemLanguageResultExecution timeMemory
706214bLICFactories (JOI14_factories)C++17
100 / 100
4202 ms221248 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 = 22; 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; } int n, m; ll ans; vector<vector<pii>> adj; vl dist[maxN]; bool used[maxN]; int st[maxN], en[maxN]; int tim; vii tour; std::vector<int> parent, stree; vector<ll> nearest; void DOO(std::vector<std::vector<pii>>& _adj){ parent.resize((int)_adj.size()); stree.resize((int)_adj.size()); nearest.assign((int)_adj.size(), INFLL); } int dfssize(int, int); int dfscentroid(int, int, int); void dfs(int node, ll d, int p){ dist[node].push_back(d); for (pii x:adj[node]){ if (x.ft!=p && !used[x.ft]){ dfs(x.ft, d+x.sd, node); } } } void build(int node = 1, int par = -1, ll depcent = 1){ int n = dfssize(node, par); int centroid = dfscentroid(node, par, n); parent[centroid] = par; used[centroid] = true; dfs(centroid, 0, par); for (const pii &y:adj[centroid]) { int x = y.ft; if (x!=par && !used[x]) build(x, centroid, depcent+1); } } int dfssize(int node, int par){ stree[node] = 1; for (const pii &y:adj[node]){ int x = y.ft; if (x!=par && !used[x]) { dfssize(x, node); stree[node] += stree[x]; } } return stree[node]; } int dfscentroid(int node, int par, int n){ for (const pii &y:adj[node]){ int x = y.ft; if (x!=par && !used[x] && stree[x]>n/2) return dfscentroid(x, node, n); } return node; } void color(int node){ nearest[node] = 0; int temp = node; int up = 1; while(parent[node]!=-1){ node = parent[node]; nearest[node] = min(nearest[node], dist[temp][up++]); } } 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; int up = 1; while(parent[node]!=-1){ node = parent[node]; ret = min(ret, dist[temp][up++] + nearest[node]); } return ret; } void Init(int N, int A[], int B[], int D[]){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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}); } DOO(adj); build(0, -1); for (int i = 0;i<n;i++) { reverse(all(dist[i])); } } long long Query(int S, int X[], int T, int Y[]){ ll res = INFLL; for (int i = 0;i<S;i++) color(X[i]); for (int i = 0;i<T;i++) res = min(res, getnearest(Y[i])); for (int i = 0;i<S;i++) decolor(X[i]); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...