oj.uz

Submission #336518

# Submission time Handle Problem Language Result Execution time Memory
336518 2020-12-15T13:50:54 Z YJU Designated Cities (JOI19_designated_cities) C++14
16 / 100
 425 ms 52876 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,x,wa,wb,y,ans[N],down[N],fr[N],fn[N],dsum,q,sub[N][2],vis[N],rta,rtb,lst[N];
vector<pair<ll,pll> > v[N];
priority_queue<ll> pq;

void PDFS(ll nd,ll Parent){
	sub[nd][0]=sub[nd][1]=down[nd]=nd;
	for(auto i:v[nd]){
		if(i.X==Parent)continue;
		fn[i.X]=fn[nd]+i.Y.Y;
		fr[i.X]=fr[nd]+i.Y.X;
		dsum+=i.Y.X;
		PDFS(i.X,nd);
		down[nd]=(fr[down[i.X]]>fr[down[nd]]?down[i.X]:down[nd]);
		ll id=down[i.X];
		if(fr[sub[nd][0]]<=fr[id])swap(id,sub[nd][0]);
		if(fr[sub[nd][1]]<=fr[id])swap(id,sub[nd][1]);
	}
}

void RDFS(ll nd,ll pa){
	lst[nd]=pa;
	for(auto i:v[nd]){
		if(i.X==pa)continue;
		RDFS(i.X,nd);
	}
}

void DFS(ll nd,ll pa){
	for(auto i:v[nd]){
		if(i.X==pa||vis[i.X])continue;
		DFS(i.X,nd);
		fr[i.X]+=i.Y.X;
		fr[nd]=max(fr[nd],fr[i.X]);
	}
	ll cnt=0;
	for(auto i:v[nd]){
		if(cnt==0&&fr[i.X]==fr[nd])++cnt;
		else{
			pq.push(fr[i.X]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP(i,n-1){
		cin>>x>>y>>wa>>wb;
		v[x].pb(mp(y,mp(wa,wb)));
		v[y].pb(mp(x,mp(wb,wa)));
	}
	PDFS(1,0);
	REP1(i,n)ans[i]=INF;
	REP1(i,n){
		ans[1]=min(ans[1],dsum+fn[i]-fr[i]);
		if(dsum+fn[i]+fr[i]-(fr[sub[i][0]]+fr[sub[i][1]])<ans[2]){
			rta=sub[i][0];rtb=sub[i][1];
			ans[2]=dsum+fn[i]+fr[i]-(fr[sub[i][0]]+fr[sub[i][1]]);
		}
	}
	memset(fn,0,sizeof(fn));
	memset(fr,0,sizeof(fr));
	dsum=0;
	RDFS(rta,0);
	vis[rta]=1;
	while(rtb!=rta){
		vis[rtb]=1;
		rtb=lst[rtb];
	}
	REP1(i,n){
		if(vis[i]){
			DFS(i,0);
			pq.push(fr[i]);
		}
	}
	
	for(int i=3;i<=n;i++){
		if(SZ(pq)==0){ans[i]=ans[i-1];continue;}
		ans[i]=ans[i-1]-pq.top()+dsum;
		pq.pop();
	}
	cin>>q;
	while(q--){
		cin>>x;
		cout<<ans[x]<<"\n";
	}
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Incorrect 5 ms 8172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 352 ms 32360 KB Output is correct
3 Correct 381 ms 50188 KB Output is correct
4 Correct 341 ms 31592 KB Output is correct
5 Correct 340 ms 32160 KB Output is correct
6 Correct 365 ms 35172 KB Output is correct
7 Correct 295 ms 34076 KB Output is correct
8 Correct 389 ms 50784 KB Output is correct
9 Correct 214 ms 34300 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 366 ms 32444 KB Output is correct
3 Correct 425 ms 52876 KB Output is correct
4 Correct 349 ms 31336 KB Output is correct
5 Correct 342 ms 32160 KB Output is correct
6 Correct 361 ms 35560 KB Output is correct
7 Correct 234 ms 34064 KB Output is correct
8 Correct 383 ms 45020 KB Output is correct
9 Correct 214 ms 34192 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Incorrect 5 ms 8172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 352 ms 32360 KB Output is correct
3 Correct 381 ms 50188 KB Output is correct
4 Correct 341 ms 31592 KB Output is correct
5 Correct 340 ms 32160 KB Output is correct
6 Correct 365 ms 35172 KB Output is correct
7 Correct 295 ms 34076 KB Output is correct
8 Correct 389 ms 50784 KB Output is correct
9 Correct 214 ms 34300 KB Output is correct
10 Correct 5 ms 8172 KB Output is correct
11 Correct 366 ms 32444 KB Output is correct
12 Correct 425 ms 52876 KB Output is correct
13 Correct 349 ms 31336 KB Output is correct
14 Correct 342 ms 32160 KB Output is correct
15 Correct 361 ms 35560 KB Output is correct
16 Correct 234 ms 34064 KB Output is correct
17 Correct 383 ms 45020 KB Output is correct
18 Correct 214 ms 34192 KB Output is correct
19 Correct 5 ms 8172 KB Output is correct
20 Incorrect 360 ms 32360 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Incorrect 5 ms 8172 KB Output isn't correct
3 Halted 0 ms 0 KB -