oj.uz

Submission #918469

# Submission time Handle Problem Language Result Execution time Memory
918469 2024-01-29T21:21:49 Z amirhoseinfar1385 Designated Cities (JOI19_designated_cities) C++17
100 / 100
 778 ms 210484 KB 
#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;
}
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";
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 146004 KB Output is correct
2 Correct 74 ms 146000 KB Output is correct
3 Correct 75 ms 145896 KB Output is correct
4 Correct 73 ms 146000 KB Output is correct
5 Correct 71 ms 146056 KB Output is correct
6 Correct 71 ms 146000 KB Output is correct
7 Correct 75 ms 146004 KB Output is correct
8 Correct 78 ms 146052 KB Output is correct
9 Correct 72 ms 146004 KB Output is correct
10 Correct 74 ms 146004 KB Output is correct
11 Correct 72 ms 146096 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 146104 KB Output is correct
2 Correct 500 ms 166428 KB Output is correct
3 Correct 713 ms 203604 KB Output is correct
4 Correct 475 ms 166604 KB Output is correct
5 Correct 464 ms 166300 KB Output is correct
6 Correct 538 ms 171720 KB Output is correct
7 Correct 424 ms 166532 KB Output is correct
8 Correct 704 ms 204616 KB Output is correct
9 Correct 334 ms 168128 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 145880 KB Output is correct
2 Correct 493 ms 166580 KB Output is correct
3 Correct 706 ms 209864 KB Output is correct
4 Correct 470 ms 166484 KB Output is correct
5 Correct 488 ms 166436 KB Output is correct
6 Correct 526 ms 172468 KB Output is correct
7 Correct 397 ms 167748 KB Output is correct
8 Correct 612 ms 190256 KB Output is correct
9 Correct 343 ms 167868 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 146004 KB Output is correct
2 Correct 74 ms 146000 KB Output is correct
3 Correct 75 ms 145896 KB Output is correct
4 Correct 73 ms 146000 KB Output is correct
5 Correct 71 ms 146056 KB Output is correct
6 Correct 71 ms 146000 KB Output is correct
7 Correct 75 ms 146004 KB Output is correct
8 Correct 78 ms 146052 KB Output is correct
9 Correct 72 ms 146004 KB Output is correct
10 Correct 74 ms 146004 KB Output is correct
11 Correct 72 ms 146096 KB Output is correct
12 Correct 72 ms 146056 KB Output is correct
13 Correct 74 ms 146260 KB Output is correct
14 Correct 74 ms 146324 KB Output is correct
15 Correct 73 ms 146256 KB Output is correct
16 Correct 76 ms 146276 KB Output is correct
17 Correct 75 ms 146256 KB Output is correct
18 Correct 80 ms 146520 KB Output is correct
19 Correct 72 ms 146260 KB Output is correct
20 Correct 76 ms 146264 KB Output is correct
21 Correct 77 ms 146256 KB Output is correct
22 Correct 78 ms 146188 KB Output is correct
23 Correct 73 ms 146256 KB Output is correct
24 Correct 82 ms 146216 KB Output is correct
25 Correct 74 ms 146516 KB Output is correct
26 Correct 84 ms 146256 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 146104 KB Output is correct
2 Correct 500 ms 166428 KB Output is correct
3 Correct 713 ms 203604 KB Output is correct
4 Correct 475 ms 166604 KB Output is correct
5 Correct 464 ms 166300 KB Output is correct
6 Correct 538 ms 171720 KB Output is correct
7 Correct 424 ms 166532 KB Output is correct
8 Correct 704 ms 204616 KB Output is correct
9 Correct 334 ms 168128 KB Output is correct
10 Correct 73 ms 145880 KB Output is correct
11 Correct 493 ms 166580 KB Output is correct
12 Correct 706 ms 209864 KB Output is correct
13 Correct 470 ms 166484 KB Output is correct
14 Correct 488 ms 166436 KB Output is correct
15 Correct 526 ms 172468 KB Output is correct
16 Correct 397 ms 167748 KB Output is correct
17 Correct 612 ms 190256 KB Output is correct
18 Correct 343 ms 167868 KB Output is correct
19 Correct 73 ms 146004 KB Output is correct
20 Correct 471 ms 166572 KB Output is correct
21 Correct 778 ms 210484 KB Output is correct
22 Correct 505 ms 166352 KB Output is correct
23 Correct 464 ms 166600 KB Output is correct
24 Correct 478 ms 166544 KB Output is correct
25 Correct 476 ms 166516 KB Output is correct
26 Correct 451 ms 166544 KB Output is correct
27 Correct 473 ms 166764 KB Output is correct
28 Correct 505 ms 171408 KB Output is correct
29 Correct 493 ms 166896 KB Output is correct
30 Correct 495 ms 166484 KB Output is correct
31 Correct 396 ms 166472 KB Output is correct
32 Correct 627 ms 191944 KB Output is correct
33 Correct 341 ms 167872 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 146004 KB Output is correct
2 Correct 74 ms 146000 KB Output is correct
3 Correct 75 ms 145896 KB Output is correct
4 Correct 73 ms 146000 KB Output is correct
5 Correct 71 ms 146056 KB Output is correct
6 Correct 71 ms 146000 KB Output is correct
7 Correct 75 ms 146004 KB Output is correct
8 Correct 78 ms 146052 KB Output is correct
9 Correct 72 ms 146004 KB Output is correct
10 Correct 74 ms 146004 KB Output is correct
11 Correct 72 ms 146096 KB Output is correct
12 Correct 79 ms 146104 KB Output is correct
13 Correct 500 ms 166428 KB Output is correct
14 Correct 713 ms 203604 KB Output is correct
15 Correct 475 ms 166604 KB Output is correct
16 Correct 464 ms 166300 KB Output is correct
17 Correct 538 ms 171720 KB Output is correct
18 Correct 424 ms 166532 KB Output is correct
19 Correct 704 ms 204616 KB Output is correct
20 Correct 334 ms 168128 KB Output is correct
21 Correct 73 ms 145880 KB Output is correct
22 Correct 493 ms 166580 KB Output is correct
23 Correct 706 ms 209864 KB Output is correct
24 Correct 470 ms 166484 KB Output is correct
25 Correct 488 ms 166436 KB Output is correct
26 Correct 526 ms 172468 KB Output is correct
27 Correct 397 ms 167748 KB Output is correct
28 Correct 612 ms 190256 KB Output is correct
29 Correct 343 ms 167868 KB Output is correct
30 Correct 72 ms 146056 KB Output is correct
31 Correct 74 ms 146260 KB Output is correct
32 Correct 74 ms 146324 KB Output is correct
33 Correct 73 ms 146256 KB Output is correct
34 Correct 76 ms 146276 KB Output is correct
35 Correct 75 ms 146256 KB Output is correct
36 Correct 80 ms 146520 KB Output is correct
37 Correct 72 ms 146260 KB Output is correct
38 Correct 76 ms 146264 KB Output is correct
39 Correct 77 ms 146256 KB Output is correct
40 Correct 78 ms 146188 KB Output is correct
41 Correct 73 ms 146256 KB Output is correct
42 Correct 82 ms 146216 KB Output is correct
43 Correct 74 ms 146516 KB Output is correct
44 Correct 84 ms 146256 KB Output is correct
45 Correct 73 ms 146004 KB Output is correct
46 Correct 471 ms 166572 KB Output is correct
47 Correct 778 ms 210484 KB Output is correct
48 Correct 505 ms 166352 KB Output is correct
49 Correct 464 ms 166600 KB Output is correct
50 Correct 478 ms 166544 KB Output is correct
51 Correct 476 ms 166516 KB Output is correct
52 Correct 451 ms 166544 KB Output is correct
53 Correct 473 ms 166764 KB Output is correct
54 Correct 505 ms 171408 KB Output is correct
55 Correct 493 ms 166896 KB Output is correct
56 Correct 495 ms 166484 KB Output is correct
57 Correct 396 ms 166472 KB Output is correct
58 Correct 627 ms 191944 KB Output is correct
59 Correct 341 ms 167872 KB Output is correct
60 Correct 72 ms 145864 KB Output is correct
61 Correct 478 ms 166344 KB Output is correct
62 Correct 740 ms 203984 KB Output is correct
63 Correct 531 ms 166748 KB Output is correct
64 Correct 496 ms 166608 KB Output is correct
65 Correct 491 ms 166404 KB Output is correct
66 Correct 509 ms 166600 KB Output is correct
67 Correct 513 ms 166560 KB Output is correct
68 Correct 499 ms 166560 KB Output is correct
69 Correct 537 ms 170956 KB Output is correct
70 Correct 514 ms 166856 KB Output is correct
71 Correct 472 ms 166628 KB Output is correct
72 Correct 450 ms 166728 KB Output is correct
73 Correct 632 ms 188172 KB Output is correct
74 Correct 364 ms 167876 KB Output is correct