oj.uz

답안 #439747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439747 2021-06-30T18:52:13 Z CSQ31 도로 폐쇄 (APIO21_roads) C++17
43 / 100
 778 ms 417704 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*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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 26 ms 30672 KB Output is correct
3 Correct 26 ms 31124 KB Output is correct
4 Correct 22 ms 28464 KB Output is correct
5 Correct 15 ms 25008 KB Output is correct
6 Correct 15 ms 25220 KB Output is correct
7 Correct 17 ms 24880 KB Output is correct
8 Correct 21 ms 28028 KB Output is correct
9 Correct 23 ms 28592 KB Output is correct
10 Correct 14 ms 24972 KB Output is correct
11 Correct 17 ms 24956 KB Output is correct
12 Correct 226 ms 146172 KB Output is correct
13 Correct 423 ms 226488 KB Output is correct
14 Correct 703 ms 281924 KB Output is correct
15 Correct 778 ms 315304 KB Output is correct
16 Correct 769 ms 315828 KB Output is correct
17 Correct 411 ms 221996 KB Output is correct
18 Correct 14 ms 24496 KB Output is correct
19 Correct 361 ms 207084 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24496 KB Output is correct
2 Correct 538 ms 347432 KB Output is correct
3 Correct 613 ms 394388 KB Output is correct
4 Correct 670 ms 417704 KB Output is correct
5 Correct 386 ms 233056 KB Output is correct
6 Correct 24 ms 31280 KB Output is correct
7 Correct 33 ms 32404 KB Output is correct
8 Correct 19 ms 28208 KB Output is correct
9 Correct 14 ms 25224 KB Output is correct
10 Correct 18 ms 25264 KB Output is correct
11 Correct 14 ms 24880 KB Output is correct
12 Correct 216 ms 161608 KB Output is correct
13 Correct 415 ms 255144 KB Output is correct
14 Correct 13 ms 24496 KB Output is correct
15 Correct 348 ms 217224 KB Output is correct
16 Correct 366 ms 238480 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24496 KB Output is correct
2 Correct 14 ms 24588 KB Output is correct
3 Correct 15 ms 24488 KB Output is correct
4 Correct 15 ms 25084 KB Output is correct
5 Correct 16 ms 25264 KB Output is correct
6 Correct 15 ms 24880 KB Output is correct
7 Correct 15 ms 25168 KB Output is correct
8 Correct 15 ms 25008 KB Output is correct
9 Correct 19 ms 25204 KB Output is correct
10 Correct 16 ms 25136 KB Output is correct
11 Correct 15 ms 25248 KB Output is correct
12 Correct 16 ms 24968 KB Output is correct
13 Correct 15 ms 25008 KB Output is correct
14 Correct 15 ms 25228 KB Output is correct
15 Correct 15 ms 24904 KB Output is correct
16 Correct 14 ms 24752 KB Output is correct
17 Correct 14 ms 24968 KB Output is correct
18 Correct 15 ms 24944 KB Output is correct
19 Correct 14 ms 24972 KB Output is correct
20 Correct 14 ms 24972 KB Output is correct
21 Correct 13 ms 24496 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24496 KB Output is correct
2 Correct 14 ms 24588 KB Output is correct
3 Correct 15 ms 24488 KB Output is correct
4 Correct 15 ms 25084 KB Output is correct
5 Correct 16 ms 25264 KB Output is correct
6 Correct 15 ms 24880 KB Output is correct
7 Correct 15 ms 25168 KB Output is correct
8 Correct 15 ms 25008 KB Output is correct
9 Correct 19 ms 25204 KB Output is correct
10 Correct 16 ms 25136 KB Output is correct
11 Correct 15 ms 25248 KB Output is correct
12 Correct 16 ms 24968 KB Output is correct
13 Correct 15 ms 25008 KB Output is correct
14 Correct 15 ms 25228 KB Output is correct
15 Correct 15 ms 24904 KB Output is correct
16 Correct 14 ms 24752 KB Output is correct
17 Correct 14 ms 24968 KB Output is correct
18 Correct 15 ms 24944 KB Output is correct
19 Correct 14 ms 24972 KB Output is correct
20 Correct 14 ms 24972 KB Output is correct
21 Correct 13 ms 24496 KB Output is correct
22 Correct 15 ms 24496 KB Output is correct
23 Correct 25 ms 29100 KB Output is correct
24 Correct 27 ms 32196 KB Output is correct
25 Correct 21 ms 28220 KB Output is correct
26 Correct 21 ms 28720 KB Output is correct
27 Correct 26 ms 31280 KB Output is correct
28 Correct 21 ms 28624 KB Output is correct
29 Correct 30 ms 31472 KB Output is correct
30 Incorrect 29 ms 31336 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 217984 KB Output is correct
2 Correct 527 ms 214652 KB Output is correct
3 Correct 471 ms 226100 KB Output is correct
4 Correct 591 ms 224620 KB Output is correct
5 Correct 475 ms 226160 KB Output is correct
6 Correct 488 ms 225112 KB Output is correct
7 Correct 533 ms 225132 KB Output is correct
8 Correct 389 ms 210072 KB Output is correct
9 Correct 526 ms 211988 KB Output is correct
10 Correct 607 ms 219524 KB Output is correct
11 Correct 468 ms 225796 KB Output is correct
12 Correct 432 ms 225448 KB Output is correct
13 Correct 14 ms 24496 KB Output is correct
14 Correct 338 ms 216028 KB Output is correct
15 Correct 367 ms 237044 KB Output is correct
16 Correct 21 ms 28532 KB Output is correct
17 Correct 20 ms 28592 KB Output is correct
18 Correct 23 ms 28492 KB Output is correct
19 Correct 22 ms 28560 KB Output is correct
20 Correct 25 ms 28556 KB Output is correct
21 Correct 348 ms 206232 KB Output is correct

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 217984 KB Output is correct
2 Correct 527 ms 214652 KB Output is correct
3 Correct 471 ms 226100 KB Output is correct
4 Correct 591 ms 224620 KB Output is correct
5 Correct 475 ms 226160 KB Output is correct
6 Correct 488 ms 225112 KB Output is correct
7 Correct 533 ms 225132 KB Output is correct
8 Correct 389 ms 210072 KB Output is correct
9 Correct 526 ms 211988 KB Output is correct
10 Correct 607 ms 219524 KB Output is correct
11 Correct 468 ms 225796 KB Output is correct
12 Correct 432 ms 225448 KB Output is correct
13 Correct 14 ms 24496 KB Output is correct
14 Correct 338 ms 216028 KB Output is correct
15 Correct 367 ms 237044 KB Output is correct
16 Correct 21 ms 28532 KB Output is correct
17 Correct 20 ms 28592 KB Output is correct
18 Correct 23 ms 28492 KB Output is correct
19 Correct 22 ms 28560 KB Output is correct
20 Correct 25 ms 28556 KB Output is correct
21 Correct 348 ms 206232 KB Output is correct
22 Correct 18 ms 24496 KB Output is correct
23 Correct 13 ms 24544 KB Output is correct
24 Correct 15 ms 24496 KB Output is correct
25 Incorrect 512 ms 209224 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 26 ms 30672 KB Output is correct
3 Correct 26 ms 31124 KB Output is correct
4 Correct 22 ms 28464 KB Output is correct
5 Correct 15 ms 25008 KB Output is correct
6 Correct 15 ms 25220 KB Output is correct
7 Correct 17 ms 24880 KB Output is correct
8 Correct 21 ms 28028 KB Output is correct
9 Correct 23 ms 28592 KB Output is correct
10 Correct 14 ms 24972 KB Output is correct
11 Correct 17 ms 24956 KB Output is correct
12 Correct 226 ms 146172 KB Output is correct
13 Correct 423 ms 226488 KB Output is correct
14 Correct 703 ms 281924 KB Output is correct
15 Correct 778 ms 315304 KB Output is correct
16 Correct 769 ms 315828 KB Output is correct
17 Correct 411 ms 221996 KB Output is correct
18 Correct 14 ms 24496 KB Output is correct
19 Correct 361 ms 207084 KB Output is correct
20 Correct 13 ms 24496 KB Output is correct
21 Correct 538 ms 347432 KB Output is correct
22 Correct 613 ms 394388 KB Output is correct
23 Correct 670 ms 417704 KB Output is correct
24 Correct 386 ms 233056 KB Output is correct
25 Correct 24 ms 31280 KB Output is correct
26 Correct 33 ms 32404 KB Output is correct
27 Correct 19 ms 28208 KB Output is correct
28 Correct 14 ms 25224 KB Output is correct
29 Correct 18 ms 25264 KB Output is correct
30 Correct 14 ms 24880 KB Output is correct
31 Correct 216 ms 161608 KB Output is correct
32 Correct 415 ms 255144 KB Output is correct
33 Correct 13 ms 24496 KB Output is correct
34 Correct 348 ms 217224 KB Output is correct
35 Correct 366 ms 238480 KB Output is correct
36 Correct 13 ms 24496 KB Output is correct
37 Correct 14 ms 24588 KB Output is correct
38 Correct 15 ms 24488 KB Output is correct
39 Correct 15 ms 25084 KB Output is correct
40 Correct 16 ms 25264 KB Output is correct
41 Correct 15 ms 24880 KB Output is correct
42 Correct 15 ms 25168 KB Output is correct
43 Correct 15 ms 25008 KB Output is correct
44 Correct 19 ms 25204 KB Output is correct
45 Correct 16 ms 25136 KB Output is correct
46 Correct 15 ms 25248 KB Output is correct
47 Correct 16 ms 24968 KB Output is correct
48 Correct 15 ms 25008 KB Output is correct
49 Correct 15 ms 25228 KB Output is correct
50 Correct 15 ms 24904 KB Output is correct
51 Correct 14 ms 24752 KB Output is correct
52 Correct 14 ms 24968 KB Output is correct
53 Correct 15 ms 24944 KB Output is correct
54 Correct 14 ms 24972 KB Output is correct
55 Correct 14 ms 24972 KB Output is correct
56 Correct 13 ms 24496 KB Output is correct
57 Correct 15 ms 24496 KB Output is correct
58 Correct 25 ms 29100 KB Output is correct
59 Correct 27 ms 32196 KB Output is correct
60 Correct 21 ms 28220 KB Output is correct
61 Correct 21 ms 28720 KB Output is correct
62 Correct 26 ms 31280 KB Output is correct
63 Correct 21 ms 28624 KB Output is correct
64 Correct 30 ms 31472 KB Output is correct
65 Incorrect 29 ms 31336 KB Output isn't correct
66 Halted 0 ms 0 KB -