oj.uz

Submission #559319

# Submission time Handle Problem Language Result Execution time Memory
559319 2022-05-09T15:23:19 Z LastRonin Road Closures (APIO21_roads) C++14
22 / 100
 657 ms 58344 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;
}
/*
5
1 0 2
2 1 3
3 0 7
4 2 7
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 17 ms 15124 KB Output is correct
3 Correct 14 ms 15128 KB Output is correct
4 Correct 15 ms 15060 KB Output is correct
5 Correct 11 ms 14476 KB Output is correct
6 Correct 11 ms 14512 KB Output is correct
7 Correct 11 ms 14432 KB Output is correct
8 Correct 14 ms 14932 KB Output is correct
9 Correct 13 ms 15060 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 241 ms 35196 KB Output is correct
13 Correct 461 ms 49028 KB Output is correct
14 Correct 580 ms 45436 KB Output is correct
15 Correct 657 ms 48624 KB Output is correct
16 Correct 626 ms 49216 KB Output is correct
17 Correct 292 ms 49228 KB Output is correct
18 Correct 8 ms 14292 KB Output is correct
19 Correct 232 ms 45704 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 108 ms 50068 KB Output is correct
3 Correct 105 ms 53700 KB Output is correct
4 Correct 116 ms 57032 KB Output is correct
5 Correct 114 ms 58344 KB Output is correct
6 Correct 13 ms 15060 KB Output is correct
7 Correct 10 ms 15188 KB Output is correct
8 Correct 10 ms 15116 KB Output is correct
9 Runtime error 26 ms 29140 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Runtime error 20 ms 29188 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Runtime error 20 ms 29188 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 52372 KB Output is correct
2 Correct 269 ms 51536 KB Output is correct
3 Correct 295 ms 57056 KB Output is correct
4 Correct 270 ms 53676 KB Output is correct
5 Correct 311 ms 57292 KB Output is correct
6 Correct 286 ms 55136 KB Output is correct
7 Correct 337 ms 55936 KB Output is correct
8 Correct 243 ms 46304 KB Output is correct
9 Correct 237 ms 54852 KB Output is correct
10 Correct 241 ms 53788 KB Output is correct
11 Correct 300 ms 54428 KB Output is correct
12 Correct 282 ms 52112 KB Output is correct
13 Correct 8 ms 14292 KB Output is correct
14 Correct 98 ms 53972 KB Output is correct
15 Correct 112 ms 58248 KB Output is correct
16 Correct 11 ms 15192 KB Output is correct
17 Correct 11 ms 15208 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 14 ms 15148 KB Output is correct
20 Correct 12 ms 15188 KB Output is correct
21 Correct 257 ms 45716 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 52372 KB Output is correct
2 Correct 269 ms 51536 KB Output is correct
3 Correct 295 ms 57056 KB Output is correct
4 Correct 270 ms 53676 KB Output is correct
5 Correct 311 ms 57292 KB Output is correct
6 Correct 286 ms 55136 KB Output is correct
7 Correct 337 ms 55936 KB Output is correct
8 Correct 243 ms 46304 KB Output is correct
9 Correct 237 ms 54852 KB Output is correct
10 Correct 241 ms 53788 KB Output is correct
11 Correct 300 ms 54428 KB Output is correct
12 Correct 282 ms 52112 KB Output is correct
13 Correct 8 ms 14292 KB Output is correct
14 Correct 98 ms 53972 KB Output is correct
15 Correct 112 ms 58248 KB Output is correct
16 Correct 11 ms 15192 KB Output is correct
17 Correct 11 ms 15208 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 14 ms 15148 KB Output is correct
20 Correct 12 ms 15188 KB Output is correct
21 Correct 257 ms 45716 KB Output is correct
22 Correct 9 ms 14420 KB Output is correct
23 Correct 9 ms 14440 KB Output is correct
24 Correct 10 ms 14420 KB Output is correct
25 Correct 265 ms 46628 KB Output is correct
26 Correct 197 ms 43288 KB Output is correct
27 Correct 298 ms 51672 KB Output is correct
28 Correct 460 ms 54348 KB Output is correct
29 Correct 393 ms 51456 KB Output is correct
30 Correct 459 ms 51104 KB Output is correct
31 Correct 536 ms 52616 KB Output is correct
32 Correct 296 ms 49996 KB Output is correct
33 Correct 487 ms 47020 KB Output is correct
34 Correct 416 ms 53400 KB Output is correct
35 Correct 336 ms 56276 KB Output is correct
36 Correct 498 ms 52208 KB Output is correct
37 Correct 475 ms 50136 KB Output is correct
38 Correct 69 ms 40140 KB Output is correct
39 Correct 115 ms 56772 KB Output is correct
40 Runtime error 31 ms 30272 KB Execution killed with signal 6
41 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 17 ms 15124 KB Output is correct
3 Correct 14 ms 15128 KB Output is correct
4 Correct 15 ms 15060 KB Output is correct
5 Correct 11 ms 14476 KB Output is correct
6 Correct 11 ms 14512 KB Output is correct
7 Correct 11 ms 14432 KB Output is correct
8 Correct 14 ms 14932 KB Output is correct
9 Correct 13 ms 15060 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 241 ms 35196 KB Output is correct
13 Correct 461 ms 49028 KB Output is correct
14 Correct 580 ms 45436 KB Output is correct
15 Correct 657 ms 48624 KB Output is correct
16 Correct 626 ms 49216 KB Output is correct
17 Correct 292 ms 49228 KB Output is correct
18 Correct 8 ms 14292 KB Output is correct
19 Correct 232 ms 45704 KB Output is correct
20 Correct 9 ms 14292 KB Output is correct
21 Correct 108 ms 50068 KB Output is correct
22 Correct 105 ms 53700 KB Output is correct
23 Correct 116 ms 57032 KB Output is correct
24 Correct 114 ms 58344 KB Output is correct
25 Correct 13 ms 15060 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 10 ms 15116 KB Output is correct
28 Runtime error 26 ms 29140 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -