oj.uz

Submission #439750

# Submission time Handle Problem Language Result Execution time Memory
439750 2021-06-30T18:55:42 Z CSQ31 Road Closures (APIO21_roads) C++17
43 / 100
 820 ms 415604 KB 
#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
vector<vector<pii>> g1(MAXN),g2(MAXN);
vector<int>par(MAXN),szz(MAXN,1),act(MAXN);
vector<ll>ans;
VII dp(2,vector<ll>(MAXN,0));
int find(int x){
	if(x == par[x])return x;
	else return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return;
	if(szz[a] > szz[b])swap(a,b);
	par[a] = b;
	szz[b]+=szz[a];
}
struct node{
	ll sum,cnt;
	ll L,R;
	node *lf=nullptr,*rg = nullptr;
	node(){}
	node(ll _L,ll _R){
		L = _L;
		R = _R;
	}
	void upd(int pos,int c){
		if(L==R){
			sum+=c*pos;
			cnt+=c;
			return;
		}
		ll tm = (L+R)/2;
		if(pos<=tm){
			if(lf == nullptr)lf = new node(L,tm);
			lf->upd(pos,c);
		}else{
			if(rg == nullptr)rg = new node(tm+1,R);
			rg->upd(pos,c);		
		}
		sum=cnt=0;
		if(lf != nullptr){
			sum+=lf->sum;
			cnt+=lf->cnt;
		}
		if(rg != nullptr){
			sum+=rg->sum;
			cnt+=rg->cnt;
		}
	}
	ll query(int v){
		//cout<<L<<" "<<R<<" "<<cnt<<" "<<v<<'\n';
		if(cnt == v)return sum;
		if(L == R)return v*1LL*L;
		ll tm = (L+R)/2;
		if(lf == nullptr)lf = new node(L,tm);
		if(lf->cnt >= v)return lf->query(v);
		else{
		    if(rg == nullptr)rg = new node(tm+1,R);
		    return lf->sum + rg->query(v-lf->cnt);	
		}
	 }
};
vector<node>seg(MAXN);
void dfs(int v,int u,ll w,int k){
	int need = sz(g1[v])-k;
	ll cur = 0;
	vector<ll>choice;
	for(auto x:g2[v]){
		if(x.fi != u){
			dfs(x.fi,v,x.se,k);
			if(dp[1][x.fi] <= dp[0][x.fi]){ //we will take this edge anyways
				cur+=dp[1][x.fi];
				need--;
			}else{
				cur+=dp[0][x.fi];
				choice.pb(dp[1][x.fi]-dp[0][x.fi]);
			}
		}
	}
	dp[0][v] = dp[1][v] = INF;
	sort(all(choice));
	if(seg[v].cnt >= need)dp[0][v] = cur + (need>0?seg[v].query(need):0);
	if(seg[v].cnt >= need-1)dp[1][v] = cur + w + (need-1>0?seg[v].query(need-1):0); //take extra edges only from inactive
	for(int i=0;i<min(sz(choice),need);i++){
		cur+=choice[i];
		int take = need-i-1;
		if(seg[v].cnt>=take)dp[0][v] = min(dp[0][v],cur + (take>0?seg[v].query(take):0));
		if(seg[v].cnt>=take-1)dp[1][v] = min(dp[1][v],cur + w + (take-1>0?seg[v].query(take-1):0));
	}
	
}
vector<ll> minimum_closure_costs(int n, vector<int> u,vector<int>v,vector<int>w){
	ans.resize(n);
	for(int i=0;i<n-1;i++){
		g1[u[i]].pb({v[i],w[i]});
		g1[v[i]].pb({u[i],w[i]});
	}
	for(int i=0;i<n;i++){
		seg[i] = node(1,1e9);
		for(auto x:g1[i])seg[i].upd(x.se,1);
	}
	vector<int>c(n);
	for(int i=0;i<n;i++){c[i] = i;par[i] = i;}
	sort(all(c),[&](int x,int y){return sz(g1[x]) > sz(g1[y]);});
	int ptr = -1;
	vector<int>vis(n);
	for(int i=n-1;i>=0;i--){
		while(ptr+1<n && sz(g1[c[ptr+1]]) > i){
			ptr++;
			int d = c[ptr];
			act[d] = 1;
			for(auto x:g1[d]){
				if(act[x.fi]){
					seg[x.fi].upd(x.se,-1); //these edges become active now,remove them from segtree
					seg[d].upd(x.se,-1);
					g2[x.fi].pb({d,x.se});
					g2[d].pb({x.fi,x.se}); 
					unite(x.fi,d);
				}
			}
		}
		vector<int>meet;
		for(int j=0;j<=ptr;j++){
			int a = find(c[j]);
			if(vis[a])continue;
			else{
				dfs(a,-1,0,i);
				meet.pb(a);
				vis[a] = 1;
				ans[i]+=dp[0][a];
			}
		}
		for(int x:meet){
			vis[x] = 0;
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 28 ms 30528 KB Output is correct
3 Correct 25 ms 31032 KB Output is correct
4 Correct 20 ms 28392 KB Output is correct
5 Correct 15 ms 24932 KB Output is correct
6 Correct 17 ms 25264 KB Output is correct
7 Correct 14 ms 24880 KB Output is correct
8 Correct 19 ms 27900 KB Output is correct
9 Correct 23 ms 28592 KB Output is correct
10 Correct 14 ms 24892 KB Output is correct
11 Correct 15 ms 24880 KB Output is correct
12 Correct 236 ms 145396 KB Output is correct
13 Correct 393 ms 225608 KB Output is correct
14 Correct 680 ms 280340 KB Output is correct
15 Correct 820 ms 313512 KB Output is correct
16 Correct 796 ms 314024 KB Output is correct
17 Correct 452 ms 220124 KB Output is correct
18 Correct 14 ms 24496 KB Output is correct
19 Correct 346 ms 206208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 554 ms 345660 KB Output is correct
3 Correct 625 ms 392368 KB Output is correct
4 Correct 645 ms 415604 KB Output is correct
5 Correct 364 ms 230804 KB Output is correct
6 Correct 24 ms 31264 KB Output is correct
7 Correct 28 ms 32308 KB Output is correct
8 Correct 19 ms 28216 KB Output is correct
9 Correct 15 ms 25180 KB Output is correct
10 Correct 15 ms 25268 KB Output is correct
11 Correct 15 ms 24880 KB Output is correct
12 Correct 211 ms 160836 KB Output is correct
13 Correct 396 ms 253808 KB Output is correct
14 Correct 14 ms 24496 KB Output is correct
15 Correct 348 ms 216048 KB Output is correct
16 Correct 416 ms 237136 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 14 ms 24524 KB Output is correct
3 Correct 13 ms 24496 KB Output is correct
4 Correct 16 ms 25136 KB Output is correct
5 Correct 17 ms 25328 KB Output is correct
6 Correct 15 ms 24928 KB Output is correct
7 Correct 15 ms 25264 KB Output is correct
8 Correct 16 ms 25008 KB Output is correct
9 Correct 14 ms 25224 KB Output is correct
10 Correct 14 ms 25136 KB Output is correct
11 Correct 15 ms 25264 KB Output is correct
12 Correct 14 ms 24916 KB Output is correct
13 Correct 15 ms 25008 KB Output is correct
14 Correct 15 ms 25220 KB Output is correct
15 Correct 15 ms 24960 KB Output is correct
16 Correct 14 ms 24716 KB Output is correct
17 Correct 14 ms 25008 KB Output is correct
18 Correct 14 ms 24912 KB Output is correct
19 Correct 14 ms 24880 KB Output is correct
20 Correct 17 ms 24876 KB Output is correct
21 Correct 15 ms 24496 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 14 ms 24524 KB Output is correct
3 Correct 13 ms 24496 KB Output is correct
4 Correct 16 ms 25136 KB Output is correct
5 Correct 17 ms 25328 KB Output is correct
6 Correct 15 ms 24928 KB Output is correct
7 Correct 15 ms 25264 KB Output is correct
8 Correct 16 ms 25008 KB Output is correct
9 Correct 14 ms 25224 KB Output is correct
10 Correct 14 ms 25136 KB Output is correct
11 Correct 15 ms 25264 KB Output is correct
12 Correct 14 ms 24916 KB Output is correct
13 Correct 15 ms 25008 KB Output is correct
14 Correct 15 ms 25220 KB Output is correct
15 Correct 15 ms 24960 KB Output is correct
16 Correct 14 ms 24716 KB Output is correct
17 Correct 14 ms 25008 KB Output is correct
18 Correct 14 ms 24912 KB Output is correct
19 Correct 14 ms 24880 KB Output is correct
20 Correct 17 ms 24876 KB Output is correct
21 Correct 15 ms 24496 KB Output is correct
22 Correct 14 ms 24496 KB Output is correct
23 Correct 23 ms 29104 KB Output is correct
24 Correct 27 ms 32092 KB Output is correct
25 Correct 20 ms 28172 KB Output is correct
26 Correct 23 ms 28800 KB Output is correct
27 Correct 32 ms 31284 KB Output is correct
28 Correct 22 ms 28592 KB Output is correct
29 Correct 26 ms 31440 KB Output is correct
30 Incorrect 27 ms 31280 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 217980 KB Output is correct
2 Correct 602 ms 214652 KB Output is correct
3 Correct 488 ms 226088 KB Output is correct
4 Correct 605 ms 224788 KB Output is correct
5 Correct 474 ms 226168 KB Output is correct
6 Correct 426 ms 225168 KB Output is correct
7 Correct 541 ms 225160 KB Output is correct
8 Correct 369 ms 209976 KB Output is correct
9 Correct 492 ms 211844 KB Output is correct
10 Correct 590 ms 219508 KB Output is correct
11 Correct 448 ms 225856 KB Output is correct
12 Correct 422 ms 225444 KB Output is correct
13 Correct 14 ms 24496 KB Output is correct
14 Correct 345 ms 216020 KB Output is correct
15 Correct 361 ms 237224 KB Output is correct
16 Correct 22 ms 28448 KB Output is correct
17 Correct 21 ms 28556 KB Output is correct
18 Correct 22 ms 28592 KB Output is correct
19 Correct 23 ms 28592 KB Output is correct
20 Correct 21 ms 28500 KB Output is correct
21 Correct 353 ms 206264 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 217980 KB Output is correct
2 Correct 602 ms 214652 KB Output is correct
3 Correct 488 ms 226088 KB Output is correct
4 Correct 605 ms 224788 KB Output is correct
5 Correct 474 ms 226168 KB Output is correct
6 Correct 426 ms 225168 KB Output is correct
7 Correct 541 ms 225160 KB Output is correct
8 Correct 369 ms 209976 KB Output is correct
9 Correct 492 ms 211844 KB Output is correct
10 Correct 590 ms 219508 KB Output is correct
11 Correct 448 ms 225856 KB Output is correct
12 Correct 422 ms 225444 KB Output is correct
13 Correct 14 ms 24496 KB Output is correct
14 Correct 345 ms 216020 KB Output is correct
15 Correct 361 ms 237224 KB Output is correct
16 Correct 22 ms 28448 KB Output is correct
17 Correct 21 ms 28556 KB Output is correct
18 Correct 22 ms 28592 KB Output is correct
19 Correct 23 ms 28592 KB Output is correct
20 Correct 21 ms 28500 KB Output is correct
21 Correct 353 ms 206264 KB Output is correct
22 Correct 13 ms 24496 KB Output is correct
23 Correct 14 ms 24496 KB Output is correct
24 Correct 17 ms 24508 KB Output is correct
25 Incorrect 561 ms 207988 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 28 ms 30528 KB Output is correct
3 Correct 25 ms 31032 KB Output is correct
4 Correct 20 ms 28392 KB Output is correct
5 Correct 15 ms 24932 KB Output is correct
6 Correct 17 ms 25264 KB Output is correct
7 Correct 14 ms 24880 KB Output is correct
8 Correct 19 ms 27900 KB Output is correct
9 Correct 23 ms 28592 KB Output is correct
10 Correct 14 ms 24892 KB Output is correct
11 Correct 15 ms 24880 KB Output is correct
12 Correct 236 ms 145396 KB Output is correct
13 Correct 393 ms 225608 KB Output is correct
14 Correct 680 ms 280340 KB Output is correct
15 Correct 820 ms 313512 KB Output is correct
16 Correct 796 ms 314024 KB Output is correct
17 Correct 452 ms 220124 KB Output is correct
18 Correct 14 ms 24496 KB Output is correct
19 Correct 346 ms 206208 KB Output is correct
20 Correct 14 ms 24496 KB Output is correct
21 Correct 554 ms 345660 KB Output is correct
22 Correct 625 ms 392368 KB Output is correct
23 Correct 645 ms 415604 KB Output is correct
24 Correct 364 ms 230804 KB Output is correct
25 Correct 24 ms 31264 KB Output is correct
26 Correct 28 ms 32308 KB Output is correct
27 Correct 19 ms 28216 KB Output is correct
28 Correct 15 ms 25180 KB Output is correct
29 Correct 15 ms 25268 KB Output is correct
30 Correct 15 ms 24880 KB Output is correct
31 Correct 211 ms 160836 KB Output is correct
32 Correct 396 ms 253808 KB Output is correct
33 Correct 14 ms 24496 KB Output is correct
34 Correct 348 ms 216048 KB Output is correct
35 Correct 416 ms 237136 KB Output is correct
36 Correct 14 ms 24496 KB Output is correct
37 Correct 14 ms 24524 KB Output is correct
38 Correct 13 ms 24496 KB Output is correct
39 Correct 16 ms 25136 KB Output is correct
40 Correct 17 ms 25328 KB Output is correct
41 Correct 15 ms 24928 KB Output is correct
42 Correct 15 ms 25264 KB Output is correct
43 Correct 16 ms 25008 KB Output is correct
44 Correct 14 ms 25224 KB Output is correct
45 Correct 14 ms 25136 KB Output is correct
46 Correct 15 ms 25264 KB Output is correct
47 Correct 14 ms 24916 KB Output is correct
48 Correct 15 ms 25008 KB Output is correct
49 Correct 15 ms 25220 KB Output is correct
50 Correct 15 ms 24960 KB Output is correct
51 Correct 14 ms 24716 KB Output is correct
52 Correct 14 ms 25008 KB Output is correct
53 Correct 14 ms 24912 KB Output is correct
54 Correct 14 ms 24880 KB Output is correct
55 Correct 17 ms 24876 KB Output is correct
56 Correct 15 ms 24496 KB Output is correct
57 Correct 14 ms 24496 KB Output is correct
58 Correct 23 ms 29104 KB Output is correct
59 Correct 27 ms 32092 KB Output is correct
60 Correct 20 ms 28172 KB Output is correct
61 Correct 23 ms 28800 KB Output is correct
62 Correct 32 ms 31284 KB Output is correct
63 Correct 22 ms 28592 KB Output is correct
64 Correct 26 ms 31440 KB Output is correct
65 Incorrect 27 ms 31280 KB Output isn't correct
66 Halted 0 ms 0 KB -