oj.uz

Submission #336503

# Submission time Handle Problem Language Result Execution time Memory
336503 2020-12-15T13:09:11 Z YJU Designated Cities (JOI19_designated_cities) C++14
16 / 100
 282 ms 51948 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];
vector<pair<ll,pll> > v[N];

void dfs1(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;
		dfs1(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]);
	}
}

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)));
	}
	dfs1(1,0);
	REP1(i,n)ans[i]=INF;
	REP1(i,n){
		ans[1]=min(ans[1],dsum+fn[i]-fr[i]);
		ans[2]=min(ans[2],dsum+fn[i]-fr[i]-(fr[sub[i][0]]+fr[sub[i][1]]-2*fr[i]));
	}
	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 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 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 4 ms 5100 KB Output is correct
2 Correct 251 ms 33900 KB Output is correct
3 Correct 282 ms 49456 KB Output is correct
4 Correct 238 ms 32492 KB Output is correct
5 Correct 240 ms 33828 KB Output is correct
6 Correct 254 ms 36332 KB Output is correct
7 Correct 215 ms 32796 KB Output is correct
8 Correct 275 ms 49772 KB Output is correct
9 Correct 165 ms 31888 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 255 ms 33900 KB Output is correct
3 Correct 280 ms 51948 KB Output is correct
4 Correct 236 ms 32492 KB Output is correct
5 Correct 236 ms 33824 KB Output is correct
6 Correct 260 ms 36588 KB Output is correct
7 Correct 176 ms 32016 KB Output is correct
8 Correct 264 ms 44012 KB Output is correct
9 Correct 159 ms 31504 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 251 ms 33900 KB Output is correct
3 Correct 282 ms 49456 KB Output is correct
4 Correct 238 ms 32492 KB Output is correct
5 Correct 240 ms 33828 KB Output is correct
6 Correct 254 ms 36332 KB Output is correct
7 Correct 215 ms 32796 KB Output is correct
8 Correct 275 ms 49772 KB Output is correct
9 Correct 165 ms 31888 KB Output is correct
10 Correct 5 ms 5100 KB Output is correct
11 Correct 255 ms 33900 KB Output is correct
12 Correct 280 ms 51948 KB Output is correct
13 Correct 236 ms 32492 KB Output is correct
14 Correct 236 ms 33824 KB Output is correct
15 Correct 260 ms 36588 KB Output is correct
16 Correct 176 ms 32016 KB Output is correct
17 Correct 264 ms 44012 KB Output is correct
18 Correct 159 ms 31504 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 254 ms 34156 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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