Submission #1033422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033422		1L1YA	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	309 ms	71764 KiB

designated_cities

//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=2e5+11;
const int lg=23;

ll n,s,q,t=1,mx=1,a[N],d[N],dp[N],st[N],et[N],val[N],par[N],ans[N],lz[N<<2];
pll seg[N<<2];
vector<pii> G1[N],G2[N];
bool mark[N];

void dfs1(int v,int p=0){
	if(d[v]>d[mx])	mx=v;
	for(auto [u,w]: G1[v])
		if(u!=p){
			d[u]=d[v]+w;
			dfs1(u,v);
			dp[v]+=dp[u]+w;
		}
}

void dfs2(int v,int p=0){
	ans[1]=min(ans[1],dp[v]);
	for(auto [u,w]: G2[v])
		if(u!=p){
			dp[u]=dp[v]+w;
			dfs2(u,v);
		}
}

void dfs3(int v,int p=0){
	a[t]=v;st[v]=t++;
	for(auto [u,w]: G1[v])
		if(u!=p){
			val[u]=w;
			par[u]=v;
			d[u]=d[v]+w;
			dfs3(u,v);
			s+=w;
		}
	et[v]=t;
}

void build(int id=1,int l=1,int r=n+1){
	if(r-l==1){
		seg[id]={d[a[l]],a[l]};
		return;
	}
	build(lc,l,mid);
	build(rc,mid,r);
	seg[id]=max(seg[lc],seg[rc]);
}

void shift(int id){
	seg[lc].F+=lz[id];lz[lc]+=lz[id];
	seg[rc].F+=lz[id];lz[rc]+=lz[id];
	lz[id]=0;
}

void update(int ql,int qr,int val,int id=1,int l=1,int r=n+1){
	if(qr<=l || ql>=r)	return;
	if(ql<=l && r<=qr){
		seg[id].F+=val;
		lz[id]+=val;
		return;
	}
	shift(id);
	update(ql,qr,val,lc,l,mid);
	update(ql,qr,val,rc,mid,r);
	seg[id]=max(seg[lc],seg[rc]);
}

int main(){
	FastIO

	cin >> n;
	for(int i=1;i<n;i++){
		int u,v,a,b;
		cin >> u >> v >> a >> b;
		G1[u].Pb({v,a});
		G1[v].Pb({u,b});
		G2[u].Pb({v,b-a});
		G2[v].Pb({u,a-b});
	}
	dfs1(1);
	ans[1]=oo;
	dfs2(1);
	mark[mx]=1;d[mx]=0;
	dfs3(mx);
	build();
	for(int i=2;i<=n;i++){
		int v=seg[1].S;
		s-=seg[1].F;
		while(!mark[v]){
			mark[v]=1;
			update(st[v],et[v],-val[v]);
			v=par[v];
		}
		ans[i]=s;
	}
	cin >> q;
	while(q--){
		int i;cin >> i;
		cout << ans[i] << endl;
	}

	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void build(int, int, int)':
designated_cities.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
designated_cities.cpp:79:13: note: in expansion of macro 'mid'
   79 |  build(lc,l,mid);
      |             ^~~
designated_cities.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
designated_cities.cpp:80:11: note: in expansion of macro 'mid'
   80 |  build(rc,mid,r);
      |           ^~~
designated_cities.cpp: In function 'void update(int, int, int, int, int, int)':
designated_cities.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
designated_cities.cpp:98:24: note: in expansion of macro 'mid'
   98 |  update(ql,qr,val,lc,l,mid);
      |                        ^~~
designated_cities.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
designated_cities.cpp:99:22: note: in expansion of macro 'mid'
   99 |  update(ql,qr,val,rc,mid,r);
      |                      ^~~

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