oj.uz

답안 #559322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559322 2022-05-09T15:25:13 Z LastRonin 도로 폐쇄 (APIO21_roads) C++14
22 / 100
 616 ms 58316 KB 
#include "roads.h"

#include <bits/stdc++.h>

#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) 
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define mp make_pair
#define pinode pair<node*, node*>
#define pb push_back
 
using namespace std;
 
const int N = 2e5 + 10;

mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	node *l = nullptr, *r = nullptr;
	ll sz = 1, y = 0, sum = 0, x = 0;
	node(ll nx) {
		x = nx;
		sz = 1;
		l = r = nullptr;
		y = bruh();
		sum = nx;
	}
} *rt[N];

void pull(node *a) {
	if(!a)return;
	a->sum = a->x;
	a->sz = 1;
	if(a->l != nullptr)a->sum += a->l->sum, a->sz += a->l->sz;
	if(a->r != nullptr)a->sum += a->r->sum, a->sz += a->r->sz;
}

node *mrg(node *a, node *b) {
	if(a == nullptr || b == nullptr)
		return (a != nullptr ? a : b);
	if(a->y > b->y) {
		a->r = mrg(a->r, b);
		pull(a);
		return a;
	}
	b->l = mrg(a, b->l);
	pull(b);
	return b;
}

pinode splitSz(node *a, ll F) {
	if(a == nullptr) 
		return mp(nullptr, nullptr);
	if((a->l ? a->l->sz : 0) >= F) {
		pinode z = splitSz(a->l, F);
		a->l = z.s;
		pull(a);
		return mp(z.f, a);					
	}
	else {
		ll dlt = F - (a->l ? a->l->sz + 1 : 1);
		pinode z = splitSz(a->r, dlt);
		a->r = z.f;
		pull(a);
		return mp(a, z.s);
	}
}

pinode splitX(node *a, ll x) {
	if(a == nullptr) 
		return mp(nullptr, nullptr);
	if(a->x <= x) {
		pinode z = splitX(a->r, x);
		a->r = z.f;
		pull(a);
		return mp(a, z.s);			
	}
	else {
		pinode z = splitX(a->l, x);
		a->l = z.s;
		pull(a);
		return mp(z.f, a);
	}
}


ll get(ll v, ll del) {
	if(del <= 0)return 0;
	pinode z = splitSz(rt[v], del);
    ll sum = (z.f ? z.f->sum : 0);
	rt[v] = mrg(z.f, z.s);
	return sum;
}

void insert(ll v, ll zn) {
	pinode z = splitX(rt[v], zn);
	node *u = new node(zn);
	rt[v] = mrg(mrg(z.f, u), z.s);
}

void dele(ll v, ll zn) {
	pinode z = splitX(rt[v], zn - 1);
	pinode z2 = splitSz(z.s, 1);
	rt[v] = mrg(z.f, z2.s);
}


ll dp[N][2];
bool was[N];

vector<int> act;
vector<pii> g[N];
vector<pii> g2[N];
vector<int> st[N];

void solve(ll v, ll p, ll x) {
	ll del = ((ll)g2[v].size()) - x;
	was[v] = 1;
	for(auto u : g[v]) {
		if(u.f != p) {
			solve(u.f, v, x);
		}
	}
	ll sum = 0;
	for(auto u : g[v]) {
		if(u.f != p) {
			sum += dp[u.f][1];
			if(dp[u.f][0] + u.s - dp[u.f][1] < 0)
				sum += dp[u.f][0] + u.s - dp[u.f][1], del--;
			else
				insert(v, dp[u.f][0] + u.s - dp[u.f][1]);		
		}
	}
	dp[v][0] = sum + get(v, del - 1);
	dp[v][1] = sum + get(v, del);	
	for(auto u : g[v]) {
		if(u.f != p) {
		    if(dp[u.f][0] + u.s - dp[u.f][1] >= 0)
				dele(v, dp[u.f][0] + u.s - dp[u.f][1]);
		}
	}
}

vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
	for(int i = 0; i <= n; i++)
		rt[i] = nullptr;	
	vector<ll> answ;
	for(int j = 0; j < n; j++)
		U[j]++, V[j]++;
	for(int i = 1; i < n; i++) {
		g2[U[i - 1]].pb(mp(V[i - 1], W[i - 1]));
		g2[V[i - 1]].pb(mp(U[i - 1], W[i - 1]));
	}	
	for(int i = 1; i <= n; i++) {
		st[g2[i].size()].pb(i);
	}
	for(int j = n - 1; j >= 0; j--) {
		for(auto v : st[j]) {
		    act.pb(v);
			for(auto u : g2[v]) {
				if((ll)g2[u.f].size() > j) {
					g[u.f].pb(mp(v, u.s));
					g[v].pb(u);
					dele(u.f, u.s);
				}
				else if((ll)g2[u.f].size() == j) {
					g[v].pb(u);									
				}
				else {
					insert(v, u.s);
				}
		   	}
		}
		ll ans = 0;
		for(auto u : act) {
			if(!was[u]) { 
				solve(u, 0, j);
				ans += dp[u][1];
			}
		}
		answ.pb(ans);
		for(auto u : act)was[u] = 0, dp[u][0] = dp[u][1] = 0;
	}           	
	reverse(answ.begin(), answ.end());
	return answ;
}
/*
7
1 0 2
2 1 3
3 2 7
4 3 7
5 4 7
6 5 7

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 14 ms 14996 KB Output is correct
3 Correct 15 ms 15136 KB Output is correct
4 Correct 12 ms 15008 KB Output is correct
5 Correct 8 ms 14472 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 14 ms 15012 KB Output is correct
9 Correct 13 ms 15100 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 12 ms 14420 KB Output is correct
12 Correct 257 ms 35112 KB Output is correct
13 Correct 432 ms 49080 KB Output is correct
14 Correct 567 ms 45360 KB Output is correct
15 Correct 616 ms 48660 KB Output is correct
16 Correct 602 ms 49300 KB Output is correct
17 Correct 263 ms 49284 KB Output is correct
18 Correct 8 ms 14304 KB Output is correct
19 Correct 229 ms 45756 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 95 ms 50072 KB Output is correct
3 Correct 108 ms 53752 KB Output is correct
4 Correct 115 ms 57080 KB Output is correct
5 Correct 112 ms 58284 KB Output is correct
6 Correct 9 ms 15060 KB Output is correct
7 Correct 10 ms 15188 KB Output is correct
8 Correct 10 ms 15136 KB Output is correct
9 Runtime error 20 ms 29172 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Runtime error 21 ms 29140 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Runtime error 21 ms 29140 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 52352 KB Output is correct
2 Correct 237 ms 51664 KB Output is correct
3 Correct 293 ms 57180 KB Output is correct
4 Correct 234 ms 53484 KB Output is correct
5 Correct 276 ms 57084 KB Output is correct
6 Correct 291 ms 55116 KB Output is correct
7 Correct 291 ms 55944 KB Output is correct
8 Correct 252 ms 46324 KB Output is correct
9 Correct 220 ms 54924 KB Output is correct
10 Correct 238 ms 53856 KB Output is correct
11 Correct 280 ms 54480 KB Output is correct
12 Correct 275 ms 52096 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 99 ms 53980 KB Output is correct
15 Correct 106 ms 58316 KB Output is correct
16 Correct 10 ms 15132 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 11 ms 15188 KB Output is correct
19 Correct 12 ms 15060 KB Output is correct
20 Correct 12 ms 15188 KB Output is correct
21 Correct 240 ms 45660 KB Output is correct

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 52352 KB Output is correct
2 Correct 237 ms 51664 KB Output is correct
3 Correct 293 ms 57180 KB Output is correct
4 Correct 234 ms 53484 KB Output is correct
5 Correct 276 ms 57084 KB Output is correct
6 Correct 291 ms 55116 KB Output is correct
7 Correct 291 ms 55944 KB Output is correct
8 Correct 252 ms 46324 KB Output is correct
9 Correct 220 ms 54924 KB Output is correct
10 Correct 238 ms 53856 KB Output is correct
11 Correct 280 ms 54480 KB Output is correct
12 Correct 275 ms 52096 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 99 ms 53980 KB Output is correct
15 Correct 106 ms 58316 KB Output is correct
16 Correct 10 ms 15132 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 11 ms 15188 KB Output is correct
19 Correct 12 ms 15060 KB Output is correct
20 Correct 12 ms 15188 KB Output is correct
21 Correct 240 ms 45660 KB Output is correct
22 Correct 10 ms 14420 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 9 ms 14412 KB Output is correct
25 Correct 197 ms 46756 KB Output is correct
26 Correct 164 ms 43264 KB Output is correct
27 Correct 239 ms 51712 KB Output is correct
28 Correct 409 ms 54324 KB Output is correct
29 Correct 350 ms 51372 KB Output is correct
30 Correct 386 ms 51116 KB Output is correct
31 Correct 443 ms 52680 KB Output is correct
32 Correct 218 ms 50008 KB Output is correct
33 Correct 408 ms 47192 KB Output is correct
34 Correct 316 ms 53392 KB Output is correct
35 Correct 248 ms 56284 KB Output is correct
36 Correct 379 ms 52224 KB Output is correct
37 Correct 420 ms 50336 KB Output is correct
38 Correct 67 ms 40136 KB Output is correct
39 Correct 107 ms 56796 KB Output is correct
40 Runtime error 22 ms 30252 KB Execution killed with signal 6
41 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 14 ms 14996 KB Output is correct
3 Correct 15 ms 15136 KB Output is correct
4 Correct 12 ms 15008 KB Output is correct
5 Correct 8 ms 14472 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 14 ms 15012 KB Output is correct
9 Correct 13 ms 15100 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 12 ms 14420 KB Output is correct
12 Correct 257 ms 35112 KB Output is correct
13 Correct 432 ms 49080 KB Output is correct
14 Correct 567 ms 45360 KB Output is correct
15 Correct 616 ms 48660 KB Output is correct
16 Correct 602 ms 49300 KB Output is correct
17 Correct 263 ms 49284 KB Output is correct
18 Correct 8 ms 14304 KB Output is correct
19 Correct 229 ms 45756 KB Output is correct
20 Correct 8 ms 14420 KB Output is correct
21 Correct 95 ms 50072 KB Output is correct
22 Correct 108 ms 53752 KB Output is correct
23 Correct 115 ms 57080 KB Output is correct
24 Correct 112 ms 58284 KB Output is correct
25 Correct 9 ms 15060 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 10 ms 15136 KB Output is correct
28 Runtime error 20 ms 29172 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -