Submission #574213

#TimeUsernameProblemLanguageResultExecution timeMemory
574213groshiFactories (JOI14_factories)C++17
0 / 100
3780 ms236668 KiB
#include<algorithm> #include<utility> #include "factories.h" using namespace std; struct wi{ vector<int> Q; vector<int> nowy; int pre=0,post=0; int rodzaj=0; long long suma[21]; int t[21]; int poz=0; long long dp[3]; bool byl=0; }*w; vector<pair<int,int> > mam,jedno; vector<int> pomoc; int pree=1,postt=1; void dodaj(int x) { for(int i=1;i<=20;i++) { w[x].t[i]=w[w[x].t[i-1]].t[i-1]; w[x].suma[i]=w[x].suma[i-1]+w[w[x].t[i-1]].suma[i-1]; } } void dfs(int x,int ojc) { w[x].pre=pree; pree++; for(int i=0;i<w[x].Q.size();i+=2) { int pom=w[x].Q[i]; if(pom==ojc) continue; w[pom].t[0]=x; w[pom].suma[0]=w[x].Q[i+1]; w[pom].poz=w[x].poz+1; dodaj(pom); dfs(pom,x); } w[x].post=postt; postt++; } long long wynik=1e18; void dfs2(int x,int ojc) { //cout<<x<<" "<<ojc<<"\n"; w[x].dp[1]=1e18; w[x].dp[2]=1e18; for(int i=0;i<w[x].nowy.size();i+=2) { int pom=w[x].nowy[i]; if(pom==ojc) continue; dfs2(pom,x); w[x].dp[1]=min(w[x].dp[1],w[pom].dp[1]+w[x].nowy[i+1]); w[x].dp[2]=min(w[x].dp[2],w[pom].dp[2]+w[x].nowy[i+1]); } w[x].dp[w[x].rodzaj]=0; wynik=min(wynik,w[x].dp[1]+w[x].dp[2]); } pair<int,int> lca(int x,int y) { if(w[x].poz>w[y].poz) swap(x,y); long long wynik=0; for(int i=20;i>=0;i--) if(w[w[y].t[i]].poz>=w[x].poz) { wynik+=w[y].suma[i]; y=w[y].t[i]; } if(x==y) return {wynik,x}; for(int i=20;i>=0;i--) if(w[x].t[i]!=w[y].t[i]) { wynik+=w[x].suma[i]; wynik+=w[y].suma[i]; x=w[x].t[i]; y=w[y].t[i]; } if(x==y) return {wynik,x}; else return {wynik+w[x].suma[0]+w[y].suma[0],w[x].t[0]}; } void Init(int n,int a[],int b[],int c[]) { int x,y,z; w=new wi[n+3]; for(int i=1;i<n;i++) { x=a[i-1]; y=b[i-1]; z=c[i-1]; w[x].Q.push_back(y); w[y].Q.push_back(x); w[x].Q.push_back(z); w[y].Q.push_back(z); } dfs(0,-1); } long long Query(int S,int a[],int T,int b[]) { int x; wynik=1e18; mam.clear(); pomoc.clear(); jedno.clear(); for(int i=1;i<=S;i++) { x=a[i-1]; w[x].rodzaj=1; jedno.push_back({w[x].pre,x}); w[x].nowy.clear(); } for(int i=1;i<=T;i++) { x=b[i-1]; w[x].rodzaj=2; jedno.push_back({w[x].pre,x}); w[x].nowy.clear(); } sort(jedno.begin(),jedno.end()); int mam=jedno.size(); for(int i=0;i<mam-1;i++)///+/- { pair<int,int> jest=lca(jedno[i].second,jedno[i+1].second); jedno.push_back({w[jest.second].pre,jest.second}); } sort(jedno.begin(),jedno.end()); pomoc.push_back(jedno[0].second); //cout<<"zyje\n"; w[jedno[0].second].byl=1; for(int i=1;i<jedno.size();i++) { x=jedno[i].second; if(w[x].byl==1) continue; w[x].byl=1; // cout<<"mam "<<x<<"\n"; while(pomoc.size()>0 && w[x].post>w[pomoc.back()].post) pomoc.pop_back(); //if(pomoc.size()==0) //cout<<"zle\n"; //cout<<"krawedz "<<pomoc.back()<<" "<<x<<" "; int odl=lca(pomoc.back(),x).first; //cout<<odl<<"\n"; w[pomoc.back()].nowy.push_back(x); w[x].nowy.push_back(pomoc.back()); w[pomoc.back()].nowy.push_back(odl); w[x].nowy.push_back(odl); pomoc.push_back(x); } dfs2(jedno[0].second,-1); //cout<<"koniec\n"; for(int i=0;i<jedno.size();i++) { w[jedno[i].second].nowy.clear(); w[jedno[i].second].dp[1]=1e18; w[jedno[i].second].dp[2]=1e18; w[jedno[i].second].byl=0; w[jedno[i].second].rodzaj=0; } return wynik; }

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int, int)':
factories.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<w[x].nowy.size();i+=2)
      |                 ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int i=1;i<jedno.size();i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for(int i=0;i<jedno.size();i++)
      |                     ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...