Submission #261383

#TimeUsernameProblemLanguageResultExecution timeMemory
261383dorijanlendvajDesignated Cities (JOI19_designated_cities)C++14
6 / 100
2105 ms157816 KiB
//DUEL #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define x first #define y second #define pii pair<int,int> #define pb push_back #define eb emplace_back #pragma GCC optimize("unroll-loops") #define shandom_ruffle(a, b) shuffle(a, b, rng) #define vi vector<int> #define vl vector<ll> #define popcnt __builtin_popcount #define popcntll __builtin_popcountll #define all(a) begin(a),end(a) using namespace std; using namespace __gnu_pbds; using ll=long long; using ull=unsigned long long; using ld=long double; int MOD=1000000007; int MOD2=998244353; vector<int> bases; const ll LLINF=1ll<<60; const char en='\n'; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void yes() {cout<<"YES"<<en; exit(0);} void no() {cout<<"NO"<<en; exit(0);} inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;} template<class T> void prVec(vector<T> w,bool fl=false) { cout<<w.size()<<en; for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' '; if (w.size()) cout<<w[w.size()-1]<<en; if (fl) cout<<flush; } void M998() { swap(MOD,MOD2); } ll raand() { ll a=rund(); a*=RAND_MAX; a+=rund(); return a; } #define rand raand ll raaand() { return raand()*(MOD-7)+raand(); } void compress(vi&v) { set<int> s; for (auto a: v) s.insert(a); vi o(all(s)); for (auto&a: v) a=lower_bound(all(o),a)-o.begin(); } void compress(vl&v) { set<ll> s; for (auto a: v) s.insert(a); vl o(all(s)); for (auto&a: v) a=lower_bound(all(o),a)-o.begin(); } string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; } string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; } ll sti(string a,int base=10) { ll k=0; for (int i=0;i<(int)a.size();++i) { k*=base; k+=a[i]-'0'; } return k; } template<class T> void eras(vector<T>& a,T b) { a.erase(find(a.begin(),a.end(),b)); } string its(ll k,int base=10) { if (k==0) return "0"; string a; while (k) { a.push_back((k%base)+'0'); k/=base; } reverse(a.begin(),a.end()); return a; } ll min(ll a,int b) { if (a<b) return a; return b; } ll min(int a,ll b) { if (a<b) return a; return b; } ll max(ll a,int b) { if (a>b) return a; return b; } ll max(int a,ll b) { if (a>b) return a; return b; } ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b,a%b); } ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } template<class T,class K> pair<T,K> mp(T a,K b) { return make_pair(a,b); } inline int mult(ll a,ll b) { return (a*b)%MOD; } inline int pot(int n,int k) { if (k==0) return 1; ll a=pot(n,k/2); a=mult(a,a); if (k%2) return mult(a,n); else return a; } int divide(int a,int b) { return mult(a,pot(b,MOD-2)); } inline int sub(int a,int b) { if (a-b>=0) return a-b; return a-b+MOD; } inline int add(int a,int b) { if (a+b>=MOD) return a+b-MOD; return a+b; } bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) { if (a%i==0) return 0; } return 1; } const int N=300010; int t,n,k; ll an[N],s; gp_hash_table<int,int> c[N]; vi ch[N]; vl dp[N]; pair<vl,vl> mer(pair<vl,vl> a,vl b) { vl x=a.x,y=a.y; vl u(x.size()+b.size()-1),v(x.size()+b.size()-1),w(y.size()+b.size()-1); for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]); for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]); for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]); vl no; for (int i=0;i<max(v.size(),w.size());++i) { ll z=0; if (i<v.size()) z=max(z,v[i]); if (i<w.size()) z=max(z,w[i]); no.pb(z); } return {u,no}; } void dfs(int i,int p=-1,ll co=0) { pair<vl,vl> so=mp(vl(2,0),vl(2,0)); vector<pii> vv; for (auto a: ch[i]) if (a!=p) { dfs(a,i,co+c[i][a]-c[a][i]); s-=c[a][i]; for (int j=1;j<dp[a].size();++j) dp[a][j]+=c[i][a]; //so=mer(so,dp[a]); vv.eb(dp[a].size(),a); } sort(all(vv)); for (auto a: vv) so=mer(so,dp[a.y]); while (so.y.size()>k+1) so.y.pop_back(); while (so.x.size()>k+1) so.x.pop_back(); for (int i=1;i<=min(k,(int)so.y.size());++i) an[i]=max(an[i],so.y[i]+co); /*cout<<i<<endl; prVec(so.x); prVec(so.y); cout<<endl;*/ dp[i]=so.x; //cout<<i<<' '<<dp[i].size()<<en; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829); cin>>n; if (n<=18) k=2000; else k=2; //k=min(n,4000000/n); for (int i=1;i<n;++i) { int a,b,x,y; cin>>a>>b>>x>>y; ch[a].pb(b); ch[b].pb(a); c[a].insert({b,x}); c[b].insert({a,y}); s+=x; s+=y; } dfs(1); int q; cin>>q; while (q--) { int u; cin>>u; assert(u<=k); cout<<s-an[u]<<en; } }

Compilation message (stderr)

designated_cities.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > mer(std::pair<std::vector<long long int>, std::vector<long long int> >, std::vector<long long int>)':
designated_cities.cpp:213:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:213:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:214:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:214:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:215:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:215:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:217:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<max(v.size(),w.size());++i)
               ~^~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:220:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i<v.size()) z=max(z,v[i]);
       ~^~~~~~~~~
designated_cities.cpp:221:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i<w.size()) z=max(z,w[i]);
       ~^~~~~~~~~
designated_cities.cpp: In function 'void dfs(int, int, ll)':
designated_cities.cpp:235:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1;j<dp[a].size();++j) dp[a][j]+=c[i][a];
                ~^~~~~~~~~~~~~
designated_cities.cpp:241:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (so.y.size()>k+1) so.y.pop_back();
         ~~~~~~~~~~~^~~~
designated_cities.cpp:242:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (so.x.size()>k+1) so.x.pop_back();
         ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...