Submission #996268

#	Time	Username	Problem	Language	Result	Execution time	Memory
996268		Dzadzo	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	403 ms	74944 KiB

designated_cities

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 200000
using namespace std;
int t[4*MAXN+1];
int lazy[4*MAXN+1];
void push(int v){
	t[2*v]+=lazy[v];
	t[2*v+1]+=lazy[v];
	lazy[2*v]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta){
	if (l>r)return;
	if (tl==l && tr==r){
		t[v]+=delta;
		lazy[v]+=delta;
	}else{
		push(v);
		int tm=(tl+tr)/2;
		up(v*2,tl,tm,l,min(r,tm),delta);
		up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
		t[v]=max(t[v*2],t[v*2+1]);
	}
}
vector<vector<pair<int,pii>>> adj(MAXN+1);
int dp[MAXN+1];
int s[MAXN+1];
int timer=0;
int ind[MAXN+1];
int n;
void DFS(int v,int p,int depth){
	s[v]=1;
	ind[v]=++timer;
	up(1,1,n,ind[v],ind[v],depth);
	for (auto X:adj[v]){
		int to=X.F;
		int x=X.S.F;
		int y=X.S.S;
		if (to!=p){
			DFS(to,v,depth+x);
			dp[v]+=dp[to]+y;
			s[v]+=s[to];
		}
	}
}
pii best={0,0};
int ans=0;
void reroot(int v,int p){
	best=max(best,{dp[v]+t[1],v});
	ans=max(ans,dp[v]);
	for (auto X:adj[v]){
		int to=X.F;
		int x=X.S.F;
		int y=X.S.S;
		if (to==p)continue;
		int dpv=dp[v],dpto=dp[to];
		dp[v]-=dp[to]+y;
		dp[to]+=dp[v]+x;
		up(1,1,n,1,n,y);
		up(1,1,n,ind[to],ind[to]+s[to]-1,-x-y);
		reroot(to,v);
		dp[v]=dpv;
		dp[to]=dpto;
		up(1,1,n,1,n,-y);
		up(1,1,n,ind[to],ind[to]+s[to]-1,x+y);
	}
}
pii val[MAXN+1];
int a[MAXN+1];
int root;
void dfs(int v,int p){
 
	val[v]={0,v};
	for (auto X:adj[v]){
		int to=X.F;
		int x=X.S.F;
		int y=X.S.S;
		if (to==p)continue;
		dfs(to,v);
		val[v]=max(val[v],{val[to].F+x,val[to].S});
	}
	for (auto X:adj[v]){
		int to=X.F;
		int x=X.S.F;
		int y=X.S.S;
		if (to==p)continue;
		if (val[to].S!=val[v].S || v==root)a[val[to].S]=val[to].F+x;
	}	
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	int cost=0;
	for (int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		int x,y;
		cin>>x>>y;
		adj[u].pb({v,{x,y}});
		adj[v].pb({u,{y,x}});
		cost+=y+x;
	}
	DFS(1,0,0);
	reroot(1,0);
	root=best.S;
	dfs(root,0);
	int q;
	cin>>q;
	vi V={INF};
	for (int i=1;i<=n;i++)V.pb(a[i]);
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	vi p(n+1);
	for (int i=1;i<=n;i++)p[i]=p[i-1]+V[i];
	while (q--){
		int e;
		cin>>e;
		if (e==1)cout<<cost-ans<<'\n';else{
			cout<<cost-p[e-1]-best.F+p[1]<<'\n';
		}
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs(long long int, long long int)':
designated_cities.cpp:93:7: warning: unused variable 'y' [-Wunused-variable]
   93 |   int y=X.S.S;
      |       ^
designated_cities.cpp:101:7: warning: unused variable 'y' [-Wunused-variable]
  101 |   int y=X.S.S;
      |       ^

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