oj.uz

Submission #918425

# Submission time Handle Problem Language Result Execution time Memory
918425 2024-01-29T19:56:01 Z amirhoseinfar1385 Designated Cities (JOI19_designated_cities) C++17
0 / 100
 3 ms 4956 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2000+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 resr[maxn][maxn],kaf=0,res[maxn],suma,n,cnt=0,val[maxn];

set<pair<long long,long long>>dp[maxn];
void merge(long long u,long long v){
	long long fu=u;
	if((long long)dp[u].size()<(long long)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){
//	dp[u].clear();
//	if(p!=-1){
//		dp[u].insert(make_pair(0,u));
//	}
	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];
			}			
		}
	}
//	auto x=*dp[u].rbegin();
//	dp[u].erase(x);
//	x.first+=len;
//	dp[u].insert(x);
	val[rt]+=len;
	return rt;
}


void solve(long long u){
	kaf=0;
	dfs(u);
	resr[u][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++){
		resr[u][i]=resr[u][i-1];
		if((long long)tof.size()>0){
			resr[u][i]+=(tof.back());
			tof.pop_back();
		}
		if(i==2){
			if(res[i]<resr[u][i-1]){
				cnt=1;
			}
			else if(res[i]==resr[u][i-1]){
				cnt++;				
			}
		}
		res[i]=max(res[i],resr[u][i-1]);
	}
}

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);
	}
	for(long long i=1;i<=n;i++){
		solve(i);
	}
/*	for(long long i=1;i<=n;i++){
		long long f=1;
		for(long long j=2;j<=n;j++){
			if(resr[i][j-1]!=res[j]){
				f=0;
			}
		}
		if(f){
			cnt++;
		}
	}
	if(cnt==1){
    	assert(0);
	}*/
	if(cnt>2){
		assert(0);
	}
	long long q;
	cin>>q;
	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";
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 3 ms 4956 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 3 ms 4956 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 3 ms 4956 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -