Submission #930954

#TimeUsernameProblemLanguageResultExecution timeMemory
930954idiotcomputer공장들 (JOI14_factories)C++11
100 / 100
4045 ms377432 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; #define pb push_back #define ll long long int #define pii pair<int,ll> #define f first #define s second const int mxN = 5*1e5; const ll llmax = (ll) 1e17; vector<pii> adj[mxN]; vector<pii> ctree[mxN]; int ssize[mxN]; ll res[mxN]; bool vis[mxN]; void dfs(int node, int p){ ssize[node] = 1; for (pii next : adj[node]){ if (next.f == p || vis[next.f]){ continue; } dfs(next.f,node); ssize[node] += ssize[next.f]; } } void dfs2(int node, int p, int cent, ll cdepth){ ctree[node].pb({cent,cdepth}); for (pii next : adj[node]){ if (next.f == p || vis[next.f]){ continue; } dfs2(next.f,node,cent,cdepth+next.s); } } int gcentroid(int node, int p, int tot){ for (pii next : adj[node]){ if (next.f == p || vis[next.f]){ continue; } if (ssize[next.f] > tot){ return gcentroid(next.f,node,tot); } } return node; } void cdecomp(int node){ dfs(node,-1); int centroid = gcentroid(node,-1,ssize[node]/2); dfs2(centroid,-1,centroid,0); vis[centroid] = 1; for (pii next : adj[centroid]){ if (!vis[next.f]){ cdecomp(next.f); } } } void upd(int node, bool w){ for (pii next : ctree[node]){ if (w){ res[next.f] = min(res[next.f],next.s); } else { res[next.f] = llmax; } } } ll query(int node){ ll tot = llmax; for (pii next : ctree[node]){ tot = min(tot, next.s + res[next.f]); } return tot; } void Init(int N, int A[], int B[], int D[]){ for (int i =0; i < N-1; i++){ adj[A[i]].pb({B[i],D[i]}); adj[B[i]].pb({A[i],D[i]}); } memset(vis,0,sizeof(vis)); cdecomp(0); for (int i = 0; i < N; i++){ res[i] = llmax; } } long long Query(int S, int X[], int T, int Y[]){ vector<int> temp; ll tot = llmax; for (int i = 0; i < S; i++){ upd(X[i],true); temp.pb(X[i]); } for (int i = 0; i < T; i++){ tot = min(tot, query(Y[i])); } for (int i =0; i < S; i++){ upd(temp[i],false); } return tot; } /* int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,q; cin >> n >> q; int a,b,d; for (int i =0; i < n-1; i++){ cin >> a >> b >> d; adj[a].pb({b,d}); adj[b].pb({a,d}); } memset(vis,0,sizeof(vis)); cdecomp(0); for (int i = 0; i < n; i++){ res[i] = llmax; } int s,t; ll tot; vector<int> temp; for (int i =0; i < q; i++){ cin >> s >> t; tot = llmax; temp.clear(); for (int j = 0; j < s; j++){ cin >> a; upd(a,true); temp.pb(a); } for (int j = 0; j < t; j++){ cin >> a; tot = min(tot, query(a)); } for (int j =0; j < s; j++){ upd(temp[j],false); } cout << tot << '\n'; } return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...