oj.uz

Submission #336514

# Submission time Handle Problem Language Result Execution time Memory
336514 2020-12-15T13:44:18 Z YJU Designated Cities (JOI19_designated_cities) C++14
16 / 100
 354 ms 50272 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;
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]);
	}
}

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

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;
	DFS(rta,0);
	REP1(i,n)if(vis[i])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 305 ms 30388 KB Output is correct
3 Correct 346 ms 50236 KB Output is correct
4 Correct 288 ms 30464 KB Output is correct
5 Correct 291 ms 30752 KB Output is correct
6 Correct 307 ms 32876 KB Output is correct
7 Correct 273 ms 30028 KB Output is correct
8 Correct 354 ms 49384 KB Output is correct
9 Correct 213 ms 30736 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 307 ms 30440 KB Output is correct
3 Correct 353 ms 50272 KB Output is correct
4 Correct 295 ms 30404 KB Output is correct
5 Correct 299 ms 30752 KB Output is correct
6 Correct 314 ms 33772 KB Output is correct
7 Correct 224 ms 30736 KB Output is correct
8 Correct 333 ms 43616 KB Output is correct
9 Correct 210 ms 30736 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 305 ms 30388 KB Output is correct
3 Correct 346 ms 50236 KB Output is correct
4 Correct 288 ms 30464 KB Output is correct
5 Correct 291 ms 30752 KB Output is correct
6 Correct 307 ms 32876 KB Output is correct
7 Correct 273 ms 30028 KB Output is correct
8 Correct 354 ms 49384 KB Output is correct
9 Correct 213 ms 30736 KB Output is correct
10 Correct 5 ms 8172 KB Output is correct
11 Correct 307 ms 30440 KB Output is correct
12 Correct 353 ms 50272 KB Output is correct
13 Correct 295 ms 30404 KB Output is correct
14 Correct 299 ms 30752 KB Output is correct
15 Correct 314 ms 33772 KB Output is correct
16 Correct 224 ms 30736 KB Output is correct
17 Correct 333 ms 43616 KB Output is correct
18 Correct 210 ms 30736 KB Output is correct
19 Correct 5 ms 8172 KB Output is correct
20 Incorrect 307 ms 30444 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 -