Submission #918468

#	Time	Username	Problem	Language	Result	Execution time	Memory
918468		amirhoseinfar1385	Designated Cities (JOI19_designated_cities)	C++17	Compilation error	0 ms	0 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
struct yal{
	long long u,v,wu,wv,jam;
	long long getad(long long fu){
		if(fu==u){
			return v;
		}
		return u;
	}
	long long getval(long long fu){
		if(fu==u){
			return wu;
		}
		return wv;
	}
}alle[maxn];
vector<long long>adj[maxn];
long long n,val[maxn],res[maxn],suma=0,kaf=0,valpre[maxn];
deque<long long>mxd[maxn];
pair<long long,long long>stf[maxn];
long long timea=0; 

void predfs(long long u,long long par=-1){
	mxd[u].push_back(0);
	mxd[u].push_back(0);
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v!=par){
			predfs(v,u);
			mxd[u].push_back(mxd[v].back()+alle[x].getval(v));
			sort(mxd[u].begin(),mxd[u].end());
			mxd[u].pop_front();
		}
	}
	stf[u].second=timea;
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v==par){
			valpre[stf[u].first]+=alle[x].getval(u);
			valpre[stf[u].second+1]-=alle[x].getval(u);
			valpre[0]+=alle[x].getval(v);
			valpre[stf[u].first]-=alle[x].getval(v);
			valpre[stf[u].second+1]+=alle[x].getval(v);
		}
	}
}

void dfsdown(long long u,long long par=-1,long long len=0){
	mxd[u].push_back(len);
	sort(mxd[u].begin(),mxd[u].end());
	mxd[u].pop_front();
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v!=par){
			if(mxd[u].back()==mxd[v].back()+alle[x].getval(v)){
				dfsdown(v,u,mxd[u][0]+alle[x].getval(u));
			}
			else{
				dfsdown(v,u,mxd[u].back()+alle[x].getval(u));
			}
		}
	}
}

long long getd(){
	predfs(1);
	dfsdown(1);
	for(long long i=1;i<maxn;i++){
		valpre[i]+=valpre[i-1];
	}
	long long rt=1,mx=0;
	for(long long i=1;i<=n;i++){
		res[1]=max(res[1],valpre[i]);
		if(mx<=valpre[stf[i].first]+mxd[i].back()){
			rt=i;
			mx=valpre[stf[i].first]+mxd[i].back();
		}
	}
	return rt;
}
 
void merge(long long u,long long v){
	long long fu=u;
	if((long long)dp[u].size()<dp[v].size()){
		swap(u,v);
	}
	for(auto x:dp[v]){
		dp[u].insert(x);
	}
	if(fu!=u){
		swap(dp[fu],dp[u]);
	}
}

long long dfs(long long u,long long p=-1,long long len=0){
	val[u]=0;
	long long mx=0,rt=u;
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v!=p){
			kaf+=alle[x].getval(u);
			int z=dfs(v,u,alle[x].getval(v));
		//	merge(u,v);
			if(val[z]>=mx){
				rt=z;
				mx=val[z];
			}			
		}
	}
	val[rt]+=len;
	return rt;
}
 
 
void solve(long long u){
	kaf=0;
	dfs(u);
	vector<long long>hamres(n+2);
	hamres[0]=kaf;
	vector<long long>tof;
	for(int i=1;i<=n;i++){
		tof.push_back(val[i]);
	}
	sort(tof.begin(),tof.end());
	for(long long i=1;i<=n;i++){
		hamres[i]=hamres[i-1];
		if((long long)tof.size()>0){
			hamres[i]+=(tof.back());
			tof.pop_back();
		}
		res[i]=max(res[i],hamres[i-1]);
	}
}

void dovombebad(){
	long long g=getd();
	//cout<<"wtf: "<<g<<endl;
	solve(g);
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(long long i=0;i<n-1;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].wv>>alle[i].wu;
		alle[i].jam=alle[i].wu+alle[i].wv;
		suma+=alle[i].wu+alle[i].wv;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
	long long q;
	cin>>q;
	aval();
	if(n>1){
		dovombebad();
	}
	for(long long i=1;i<=n;i++){
		res[i]=suma-res[i];
	}
	for(long long i=0;i<q;i++){
		long long d;
		cin>>d;
		cout<<res[d]<<"\n";
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'void merge(long long int, long long int)':
designated_cities.cpp:88:16: error: 'dp' was not declared in this scope
   88 |  if((long long)dp[u].size()<dp[v].size()){
      |                ^~
designated_cities.cpp:91:13: error: 'dp' was not declared in this scope
   91 |  for(auto x:dp[v]){
      |             ^~
designated_cities.cpp:95:8: error: 'dp' was not declared in this scope
   95 |   swap(dp[fu],dp[u]);
      |        ^~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:159:2: error: 'aval' was not declared in this scope; did you mean 'val'?
  159 |  aval();
      |  ^~~~
      |  val