Submission #1177094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177094		8pete8	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	1703 ms	69400 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=3e5,inf=1e18,minf=-1e18,lg=30,Mxn=1e6;
//#undef int
int n,k,m,d,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
vector<pii>adj[mxn+10];
int up[mxn+10],down[mxn+10],uc[mxn+10];
void getup(int cur,int p){
	for(auto i:adj[cur]){
		if(i.f==p)uc[cur]=i.s;
		else{
			getup(i.f,cur);
			up[cur]+=up[i.f]+uc[i.f];
		}
	}
}
void getdown(int cur,int p){
	for(auto i:adj[cur])if(i.f!=p){
		down[i.f]=down[cur]+up[cur]-uc[i.f]-up[i.f]+i.s;
		getdown(i.f,cur);
	}
}
int sz[mxn+10],del[mxn+10],tin[mxn+10],tout[mxn+10],T;

struct seg{
	//get mx,lazy add update
	pii mx[4*mxn+10];
	int lazy[4*mxn+10];
	void init(){for(int i=0;i<=4*T;i++)mx[i]={minf,0},lazy[i]=0;}
	void pull(int pos){mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);}
	void apply(int pos,int x){
		mx[pos].f+=x;
		lazy[pos]+=x;
	}
	void push(int pos,int l,int r){
		if(l!=r){
			apply(pos<<1,lazy[pos]);
			apply(pos<<1|1,lazy[pos]);
		}
		lazy[pos]=0;
	}
	void modify(int qpos,pii val,int pos=1,int l=0,int r=T){
		if(l>qpos||r<qpos)return;
		if(l==r)return void(mx[pos]=val);
		push(pos,l,r);
		int mid=(l+r)>>1;
		modify(qpos,val,pos<<1,l,mid);
		modify(qpos,val,pos<<1|1,mid+1,r);
		pull(pos);
	}
	void update(int ql,int qr,int val,int pos=1,int l=0,int r=T){
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr)return void(apply(pos,val));
		push(pos,l,r);
		int mid=(l+r)>>1;
		update(ql,qr,val,pos<<1,l,mid);
		update(ql,qr,val,pos<<1|1,mid+1,r);
		pull(pos);
	}
	pii qry(int ql,int qr,int pos=1,int l=0,int r=T){
		if(l>qr||r<ql||l>r)return {minf,minf};
		if(ql<=l&&r<=qr)return mx[pos];
		push(pos,l,r);
		int mid=(l+r)>>1;
		return max(qry(ql,qr,pos<<1,l,mid),qry(ql,qr,pos<<1|1,mid+1,r));
	}
}t;

//decomp

int dist[mxn+10],ans[mxn+10],D[mxn+10];
int pa[mxn+10],node;
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i.f!=p&&!del[i.f])getsz(i.f,cur),sz[cur]+=sz[i.f];}
int getcen(int cur,int p,int need){
	for(auto i:adj[cur])if(i.f!=p&&!del[i.f]){
		if(sz[i.f]>need)return getcen(i.f,cur,need);
	}
	return cur;
}
vector<int>have;
void dfs(int cur,int p,int deg){
	tin[cur]=++T;
	have.pb(cur);
	D[cur]=deg;
	for(auto i:adj[cur])if(i.f!=p&&!del[i.f]){
		dist[i.f]=dist[cur]+i.s;
		pa[i.f]=cur;
		dfs(i.f,cur,deg);
	}
	tout[cur]=T;
}
int dead[mxn+10];
void E(int cur){
	t.modify(tin[cur],{minf,minf});
	while(!dead[cur]){
		t.update(tin[cur],tout[cur],dist[pa[cur]]-dist[cur]);
		dead[cur]=1;
		cur=pa[cur];
	}
}
void solve(int cur){
	getsz(cur,-1);
	node=getcen(cur,-1,sz[cur]/2);
	T=0;
	have.clear();
	t.init();
	dead[node]=1;
	dist[node]=0;
	for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i].f]){
		pa[adj[node][i].f]=node;
		dist[adj[node][i].f]=adj[node][i].s;
		dfs(adj[node][i].f,node,adj[node][i].f);
	}
	for(auto i:have)t.modify(tin[i],{dist[i],i});
	int sum=up[node]+down[node];
	if(have.size()<2)return;
	pii F=t.mx[1],S=max(t.qry(0,tin[D[F.s]]-1),t.qry(tout[D[F.s]]+1,T));
	sum+=F.f+S.f;
	E(F.s);
	E(S.s);
	ans[2]=max(ans[2],sum);
	for(int i=0;i<have.size()-2;i++){
		sum+=t.mx[1].f;
		E(t.mx[1].s);
		ans[i+3]=max(ans[i+3],sum);
	}
	for(auto i:have)dead[i]=0;
	del[node]=1;
	for(auto i:adj[node])if(!del[i.f])solve(i.f);
}
int32_t main(){
	fastio
	cin>>n;
	int sum=0;
	for(int i=0;i<n-1;i++){
		int a,b,c,d;cin>>a>>b>>c>>d;
		sum+=c;
		sum+=d;
		adj[a].pb({b,c});
		adj[b].pb({a,d});
	}
	getup(1,-1);
	getdown(1,-1);
	for(int i=1;i<=n;i++)ans[1]=max(ans[1],down[i]+up[i]);
	solve(1);
	int q;cin>>q;
	while(q--){
		int a;cin>>a;
		if(a>=n)cout<<0<<'\n';
		else cout<<sum-ans[a]<<'\n';
	}
}
/*
centroid decomp
for each centroid we can compute answer of [1,sz[centroid]]
we make every edge directed at centroid
then we can choose k node and add the cost of edge (from that node to centroid) directed out of centroid
*makesure not to overcount

the most optimal node to choose is the leaf?
we also need to pick atleast 2 diff node from diff subtree to make sure the centroid is the center
*/

Compilation message (stderr)

designated_cities.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
designated_cities.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
designated_cities.cpp:30:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   30 | void getup(int cur,int p){
      |                         ^
designated_cities.cpp:39:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void getdown(int cur,int p){
      |                           ^
designated_cities.cpp:51:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |         void init(){for(int i=0;i<=4*T;i++)mx[i]={minf,0},lazy[i]=0;}
      |                   ^
designated_cities.cpp:52:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |         void pull(int pos){mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);}
      |                          ^
designated_cities.cpp:53:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |         void apply(int pos,int x){
      |                                 ^
designated_cities.cpp:57:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |         void push(int pos,int l,int r){
      |                                      ^
designated_cities.cpp:64:63: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 |         void modify(int qpos,pii val,int pos=1,int l=0,int r=T){
      |                                                               ^
designated_cities.cpp:73:68: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 |         void update(int ql,int qr,int val,int pos=1,int l=0,int r=T){
      |                                                                    ^
designated_cities.cpp:82:56: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   82 |         pii qry(int ql,int qr,int pos=1,int l=0,int r=T){
      |                                                        ^
designated_cities.cpp:95:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   95 | void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i.f!=p&&!del[i.f])getsz(i.f,cur),sz[cur]+=sz[i.f];}
      |                         ^
designated_cities.cpp:96:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   96 | int getcen(int cur,int p,int need){
      |                                  ^
designated_cities.cpp:103:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  103 | void dfs(int cur,int p,int deg){
      |                               ^
designated_cities.cpp:115:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  115 | void E(int cur){
      |               ^
designated_cities.cpp:123:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  123 | void solve(int cur){
      |                   ^
designated_cities.cpp:153:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  153 | int32_t main(){
      |              ^
designated_cities.cpp: In function 'void setIO(std::string)':
designated_cities.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44