제출 #465143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465143		nathanlee726	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	516 ms	54472 KiB

designated_cities

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
vector<pair<int,pii> > g[200010];
vector<int> v;
int n,p,s=0,fa[200010],o[200010],vl[200010],mv[200010],qr[200010],so[200010],in[200010],val[200010],mvl[200010];
pii vv[200010],rt;
bool rd[200010];
void dfs(int p,int f){
	fa[p]=f;
	for(pair<int,pii> pi:g[p]){
		if(pi.X==f)continue;
		dfs(pi.X,p);
	}
}
int dfs1(int p,int f){
	int re=-1;
	for(pair<int,pii> pi:g[p]){
		if(pi.X==f)continue;
		int tr=dfs1(pi.X,p)+pi.Y.X;
		if(tr<0)continue;
		if(re==-1){
			re=tr;
		}
		else{
			if(tr>re)swap(tr,re);
			v.pb(tr);
		}
	}
	if(rd[p]){
		if(re>=0)v.pb(re);
		return -1e16;
	}
	else{
		if(re<0)return 0;
		return re;
	}
}
void dfs2(int p,int f){
	for(pair<int,pii> pi:g[p]){
		if(pi.X==f)continue;
		dfs2(pi.X,p);
		vl[p]+=(vl[pi.X]+pi.Y.Y);
		mv[pi.X]=vl[pi.X]+pi.Y.Y;
	}
}
int dfs3(int p,int f){
	int re=vl[p];
	for(pair<int,pii> pi:g[p]){
		if(pi.X==f)continue;
		vl[pi.X]+=vl[p]-mv[pi.X]+pi.Y.X;
		re=max(re,dfs3(pi.X,p)); 
	}
	return re;
}
pii dfs4(int p,int f){
	pii tp={-1,-1},tpp={-1,-1};
	for(pair<int,pii> pi:g[p]){
		if(pi.X==f)continue;
		pii tr=dfs4(pi.X,p);
		tr.X+=pi.Y.X;
		if(tr.X>=tp.X){
			swap(tp.X,tp.Y);
			swap(tpp.X,tpp.Y);
			tp.X=tr.X;
			tpp.X=tr.Y;
		}		
		else if(tr.X>=tp.Y){
			tp.Y=tr.X;
			tpp.Y=tr.Y;
		}
	}
	if(tp.X==-1){
		return {0,p};
	}
	else if(tp.Y==-1){
		if(o[2]>vl[p]-tp.X){
			o[2]=vl[p]-tp.X;
			rt={p,tpp.X};
		}
		return {tp.X,tpp.X};
	}
	else{
		if(o[2]>vl[p]-tp.X-tp.Y){
			o[2]=vl[p]-tp.X-tp.Y;
			rt={tpp.X,tpp.Y};
			bug(p,vl[p],tp.X,tp.Y,tpp.X,tpp.Y);
		}
		return {tp.X,tpp.X};
	}
}
void solve1(){
	memres(vl);
	memres(mv);		
	dfs2(0,-1);
	int x=dfs3(0,-1);
	o[1]=s-x;
}
void solve2(){
	o[2]=1e16;
	F(n)vl[i]=s-vl[i];
	dfs4(0,-1);
}
signed main(){
	IOS();
	cin>>n;
	F(n-1){
		int x,y,a,b;
		cin>>x>>y>>a>>b;
		s+=(a+b);
		--x,--y;
		g[x].pb({y,{a,b}});
		g[y].pb({x,{b,a}});
		in[x]++,in[y]++;
	} 
	int q;
	cin>>q;
	F(q)cin>>qr[i];
	solve1();
	solve2();
	int p=rt.X,pp=rt.Y;
	bug(p,pp);
	dfs(p,-1);
	int tp=pp;
	while(tp!=-1){
		if(fa[tp]!=-1)so[fa[tp]]=tp;
		rd[tp]=1;
		tp=fa[tp];
	}
	dfs1(p,-1);
	int ct=0;
	F(n)if(sz(g[i])==1)ct++;
	sort(all(v));
	int ms=0;
	for(int i=ct-1;i>=2;i--){
		ms+=v[ct-1-i];
		bug(v[ct-1-i],sz(v),ct);
		o[i]=ms;
	}
	F(q){
		if(qr[i]>=ct)cout<<0<<endl;
		else cout<<o[qr[i]]<<endl;
	}
	return 0;
}

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