oj.uz

답안 #918392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918392 2024-01-29T18:59:17 Z amirhoseinfar1385 Designated Cities (JOI19_designated_cities) C++17
0 / 100
 432 ms 82312 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
struct yal{
	int u,v,wu,wv,jam;
	int getad(int fu){
		if(fu==u){
			return v;
		}
		return u;
	}
	int getval(int fu){
		if(fu==u){
			return wu;
		}
		return wv;
	}
}alle[maxn];
vector<int>adj[maxn];
int n,val[maxn],res[maxn],suma=0,kaf=0,g;

void prea(int u=1,int p=-1){
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		int wu=alle[x].getval(u);
		if(v==p){
			val[u]+=wu;
		}
		else{
			val[1]+=wu;
			val[v]-=wu;
			prea(v,u);
		}
	}
}

void dfsa(int u=1,int p=-1){
	if(p!=-1){
		val[u]+=val[p];
	}
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v!=p){
			dfsa(v,u);
		}
	}
}


void aval(){
	prea();
	dfsa();
	int mx=0;
	for(int i=1;i<=n;i++){
		if(val[i]>=mx){
			res[1]=val[i];
			mx=val[i];
			g=i;
		}
	}
}

set<pair<int,int>>dp[maxn];

pair<int,int> getd(int u,int p=-1,int len=0){
	pair<int,int>ret=make_pair(len,u);
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v!=p){
			ret=max(ret,getd(v,u,len+alle[x].jam));
		}
	}
	return ret;
}

void merge(int u,int v){
	int fu=u;
	if((int)dp[u].size()<(int)dp[v].size()){
		swap(u,v);
	}
	for(auto x:dp[v]){
		dp[u].insert(x);
	}
	if(fu!=u){
		swap(dp[fu],dp[u]);
	}
}

void dfs(int u,int p=-1,int len=0){
	if(p!=-1){
		dp[u].insert(make_pair(0,u));
	}
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v!=p){
			//cout<<"ha: "<<u<<" "<<v<<" "<<len<<endl;
			kaf+=alle[x].getval(u);
			dfs(v,u,alle[x].getval(v));
			//cout<<"salam: "<<u<<" "<<v<<endl;
			merge(u,v);			
			//cout<<"injy vas mas "<<u<<" "<<dp[u].size()<<" "<<v<<" "<<dp[v].size()<<endl;
		}
	}
	auto x=*dp[u].rbegin();
	dp[u].erase(x);
	x.first+=len;
	dp[u].insert(x);
}

void dovombebad(){
	//int g=getd(1).second;
	//cout<<"wtf: "<<g<<endl;
	dfs(g);
	//cout<<"nagooo"<<endl;
	int ted=(int)dp[g].size();
	res[2]=kaf;
	//cout<<"by"<<ted<<endl;
	for(int i=2;i<=ted;i++){
		res[i]+=i!=2?res[i-1]:0+(*dp[g].rbegin()).first;
		dp[g].erase(*dp[g].rbegin());
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	cin>>n;
	for(int 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);
	}
	int q;
	cin>>q;
	aval();
	if(n>1){
		dovombebad();
	}
	for(int i=1;i<=n;i++){
		res[i]=suma-res[i];
	}
	for(int i=0;i<q;i++){
		int d;
		cin>>d;
		cout<<res[d]<<"\n";
	}
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Incorrect 432 ms 82312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Incorrect 432 ms 82312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -