Submission #132610

#	Time	Username	Problem	Language	Result	Execution time	Memory
132610		hamzqq9	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1041 ms	75192 KiB

designated_cities

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 200005
#define MOD 998244353
#define KOK 700		
using namespace std;

int tut21,tut22,n;
ll sub[N],mn,mn2;
vector<int> v[N];
ii e[N*2];
ll ans[N];
vector<pair<ll,int>> deep[N];

struct solve {

	int root;
	int t;
	int u[N],be[N],en[N],tut[N],dae[N],dad[N];
	ll dep[N];
	ll lazy[N*4];
	pair<ll,int> S[N*4];

	void shift(int node,ll val) {

		S[node].st+=val;
		lazy[node]+=val;

	}

	void push(int node) {

		shift(node<<1,lazy[node]);
		shift(node<<1|1,lazy[node]);

		lazy[node]=0;

	}

	void up(int node,int bas,int son,int l,int r,ll val) {

		if(bas>r || son<l) return ;

		if(bas>=l && son<=r) {

			shift(node,val);

			return ;

		}

		push(node);

		up(node<<1,bas,orta,l,r,val);
		up(node<<1|1,orta+1,son,l,r,val);

		S[node]=max(S[node<<1],S[node<<1|1]);

	}

	void build(int node,int bas,int son) {

		if(bas==son) {

			S[node]={dep[tut[bas]],tut[bas]};

			return ;

		}

		build(node<<1,bas,orta);
		build(node<<1|1,orta+1,son);

		S[node]=max(S[node<<1],S[node<<1|1]);

	}

	void dfs(int node,int ata) {

		be[node]=++t;
		tut[t]=node;

		for(int i:v[node]) {

			if(e[i].st==ata) continue ;

			dep[e[i].st]=dep[node]+e[i].nd;
			dae[e[i].st]=e[i].nd;
			dad[e[i].st]=node;

			dfs(e[i].st,node);

		}

		en[node]=t;

	}

	void build() {

		memset(u,0,sizeof(u));
		memset(lazy,0,sizeof(lazy));

		t=dep[root]=0;

		dfs(root,0);

		dep[root]=-inf;
		u[root]=1;

		build(1,1,n);

	}

	void update(int node) {

		while(!u[node]) {

		//	cerr<<node<<"\n";

			up(1,1,n,be[node],be[node],-inf);
			up(1,1,n,be[node]+1,en[node],-dae[node]);

			u[node]=1;

			node=dad[node];

		}

		//cerr<<"done\n";

		//exit(0);

	}

	pair<ll,int> getnext() {

		return S[1];

	}

	bool check() {

		//if(S[1].st>0) cerr<<S[1].nd<<"\n";

		return S[1].st>0;

	}

} solver;

void up(int node,pair<ll,int> val,int add) {

	val.st+=add;

	deep[node].pb(val);

	for(int i=sz(deep[node])-1;i>0;i--) {

		if(deep[node][i]>deep[node][i-1]) swap(deep[node][i],deep[node][i-1]);
 
	}

	if(sz(deep[node])>2) deep[node].ppb();

}

void dfs(int node,int ata,ll u) {

	if(sub[node]+u<mn) {

		mn=sub[node]+u;

	}

	if(sz(deep[node])>1) {

		if(sub[node]+u-deep[node][0].st-deep[node][1].st<mn2) {

			mn2=sub[node]+u-deep[node][0].st-deep[node][1].st;
			tut21=deep[node][0].nd;
			tut22=deep[node][1].nd;

		}

	}

	if(sub[node]+u-deep[node][0].st<mn2) {

		mn2=sub[node]+u-deep[node][0].st;
		tut21=deep[node][0].nd;
		tut22=node;

	}

	for(int i:v[node]) {

		if(e[i].st==ata) continue ;

		dfs(e[i].st,node,u+sub[node]-(sub[e[i].st]+e[i].nd)+e[i^1].nd);

	}
 
}

void dfs(int node,int ata) {

	for(int i:v[node]) {

		if(e[i].st==ata) continue ;

		dfs(e[i].st,node);

		up(node,deep[e[i].st][0],e[i].nd);

		sub[node]+=sub[e[i].st]+e[i].nd;

	}

	up(node,{0,node},0);

}

int main() {

	scanf("%d",&n);

	int ecnt=0;

	for(int i=0;i<n-1;i++) {

		int a,b,c,d;

		scanf("%d %d %d %d",&a,&b,&c,&d);

		e[ecnt]={b,c};
		e[ecnt^1]={a,d};

		v[a].pb(ecnt);
		v[b].pb(ecnt^1);

		ecnt+=2;

	}

	dfs(1,0);
	mn=mn2=inf;
	dfs(1,0,0);

	ans[1]=mn;
	ans[2]=mn2;

	solver.root=tut21;
	solver.build();

	solver.update(tut22);

	int cnt=2;

	while(solver.check()) {

		pair<ll,int> res=solver.getnext();

		ans[cnt+1]=ans[cnt]-res.st;

		++cnt;

		solver.update(res.nd);

	}

	ll last=ans[cnt];

	while(++cnt<=n) {

		ans[cnt]=last;

	}

	int q;

	scanf("%d",&q);

	while(q--) {

		int x;

		scanf("%d",&x);

		printf("%lld\n",ans[x]);

	}
 
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:237:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
designated_cities.cpp:245:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a,&b,&c,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:293:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
designated_cities.cpp:299:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

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