Submission #964594

#TimeUsernameProblemLanguageResultExecution timeMemory
964594angellaFactories (JOI14_factories)C++17
100 / 100
3632 ms194100 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> #include "factories.h" // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 5e5+23, lg = 19; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, tin[N], tout[N], tim, par[lg][N], h[N], mark[N]; ll wh[N], dp[2][N]; vector<pll> adj[N]; vector<int> tree[N]; void init(int v, int p) { par[0][v] = p, tin[v] = ++tim; for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]]; for(auto u : adj[v]) { if(u.F == p) continue; h[u.F] = h[v] + 1, wh[u.F] = wh[v] + u.S; init(u.F, v); } tout[v] = tim+1; } int getPar(int v, int dist) { for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) v=par[i][v]; return v; } int LCA(int v, int u) { if(h[v] > h[u]) swap(v, u); u = getPar(u, h[u]-h[v]); if(v == u) return v; for(int i=lg-1; i>=0; i--) { if(par[i][v] != par[i][u]) v=par[i][v], u=par[i][u]; } return par[0][v]; } void Init(int _n, int _a[], int _b[], int _d[]) { n=_n; for(int i=0; i<n-1; i++) { _a[i] ++, _b[i] ++; adj[_a[i]].pb({_b[i], _d[i]}); adj[_b[i]].pb({_a[i], _d[i]}); } init(1, 0); } bool cmp(int i, int j) { return (tin[i]<tin[j] ? true : false); } ll ans = 1e18; void dfs(int v, int p=0) { dp[0][v]=dp[1][v]=1e18; if(mark[v]==1) dp[0][v]=0; if(mark[v]==2) dp[1][v]=0; for(auto u : tree[v]) { dfs(u); dp[0][v]=min(dp[0][v], dp[0][u]+wh[u]-wh[v]); dp[1][v]=min(dp[1][v], dp[1][u]+wh[u]-wh[v]); } ans = min(ans, dp[0][v]+dp[1][v]); } ll Query(int s, int V[], int t, int U[]) { //return 2; vector<int> vec; for(int i=0;i<s;i++) { V[i]++; mark[V[i]] = 1; vec.pb(V[i]); } for(int i=0;i<t;i++) { U[i]++; mark[U[i]] = 2; vec.pb(U[i]); } sort(all(vec), cmp); int ttt = size(vec); for(int i=0; i<ttt-1; i++) vec.pb(LCA(vec[i],vec[i+1])); sort(all(vec)); vec.resize(unique(all(vec)) - vec.begin()); sort(all(vec), cmp); vector<int> st; st.pb(vec[0]); //for(auto it : vec) fuck(it); for(int i=1; i<size(vec); i++) { while(tout[st.back()]<=tin[vec[i]]) st.pop_back(); tree[st.back()].pb(vec[i]); st.pb(vec[i]); } //fuck("here"); ans = 1e18; dfs(st[0]); for(auto it : vec) { tree[it].clear(); mark[it] = 0; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...