oj.uz

Submission #559304

# Submission time Handle Problem Language Result Execution time Memory
559304 2022-05-09T15:12:42 Z LastRonin Road Closures (APIO21_roads) C++17
22 / 100
 717 ms 58372 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)a->sum += a->l->sum, a->sz += a->l->sz;
	if(a->r)a->sum += a->r->sum, a->sz += a->r->sz;
}

node *mrg(node *a, node *b) {
	if(!a || !b)
		return (a ? 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) 
		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) 
		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(g2[u.f].size() > j) {
					g[u.f].pb(mp(v, u.s));
					g[v].pb(u);
					dele(u.f, u.s);
				}
				else if(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;
}
/*
int main() {
	speed;	
	ll n;
	vector<ll> a, b, c;
	cin >> n;
	for(int i = 1; i < n; i++) {
		a.pb(0), b.pb(0), c.pb(0);
		cin >> a.back() >> b.back() >> c.back();
	}
	vector<ll> answ = minimum_closure_costs(n, a, b, c);
	ll lst = answ.size() - 1ll;
	for(auto u : answ)
		cout << u << (lst == 0 ? "" : " "), lst--;
	cout << "\n";	
}
*/

Compilation message

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:165:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |     if(g2[u.f].size() > j) {
      |        ~~~~~~~~~~~~~~~^~~
roads.cpp:170:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |     else if(g2[u.f].size() == j) {
      |             ~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 20 ms 15012 KB Output is correct
3 Correct 15 ms 15080 KB Output is correct
4 Correct 12 ms 15060 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 13 ms 14932 KB Output is correct
9 Correct 14 ms 15060 KB Output is correct
10 Correct 11 ms 14484 KB Output is correct
11 Correct 10 ms 14420 KB Output is correct
12 Correct 248 ms 35264 KB Output is correct
13 Correct 497 ms 48864 KB Output is correct
14 Correct 567 ms 45356 KB Output is correct
15 Correct 671 ms 48648 KB Output is correct
16 Correct 717 ms 49208 KB Output is correct
17 Correct 368 ms 49220 KB Output is correct
18 Correct 8 ms 14292 KB Output is correct
19 Correct 234 ms 45580 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 95 ms 50204 KB Output is correct
3 Correct 105 ms 53768 KB Output is correct
4 Correct 124 ms 57040 KB Output is correct
5 Correct 123 ms 58340 KB Output is correct
6 Correct 10 ms 15060 KB Output is correct
7 Correct 11 ms 15136 KB Output is correct
8 Correct 10 ms 15188 KB Output is correct
9 Runtime error 21 ms 29092 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 14352 KB Output is correct
2 Correct 8 ms 14300 KB Output is correct
3 Correct 10 ms 14416 KB Output is correct
4 Correct 9 ms 14472 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Runtime error 22 ms 29208 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 14352 KB Output is correct
2 Correct 8 ms 14300 KB Output is correct
3 Correct 10 ms 14416 KB Output is correct
4 Correct 9 ms 14472 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Runtime error 22 ms 29208 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 279 ms 52368 KB Output is correct
2 Correct 243 ms 51636 KB Output is correct
3 Correct 292 ms 57080 KB Output is correct
4 Correct 270 ms 53572 KB Output is correct
5 Correct 287 ms 57168 KB Output is correct
6 Correct 287 ms 55104 KB Output is correct
7 Correct 322 ms 55984 KB Output is correct
8 Correct 259 ms 46348 KB Output is correct
9 Correct 293 ms 54916 KB Output is correct
10 Correct 258 ms 53784 KB Output is correct
11 Correct 302 ms 54492 KB Output is correct
12 Correct 334 ms 52148 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 98 ms 54092 KB Output is correct
15 Correct 113 ms 58372 KB Output is correct
16 Correct 11 ms 15188 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 13 ms 15172 KB Output is correct
20 Correct 17 ms 15260 KB Output is correct
21 Correct 273 ms 45696 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 52368 KB Output is correct
2 Correct 243 ms 51636 KB Output is correct
3 Correct 292 ms 57080 KB Output is correct
4 Correct 270 ms 53572 KB Output is correct
5 Correct 287 ms 57168 KB Output is correct
6 Correct 287 ms 55104 KB Output is correct
7 Correct 322 ms 55984 KB Output is correct
8 Correct 259 ms 46348 KB Output is correct
9 Correct 293 ms 54916 KB Output is correct
10 Correct 258 ms 53784 KB Output is correct
11 Correct 302 ms 54492 KB Output is correct
12 Correct 334 ms 52148 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 98 ms 54092 KB Output is correct
15 Correct 113 ms 58372 KB Output is correct
16 Correct 11 ms 15188 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 13 ms 15172 KB Output is correct
20 Correct 17 ms 15260 KB Output is correct
21 Correct 273 ms 45696 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14292 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 216 ms 46720 KB Output is correct
26 Correct 178 ms 43288 KB Output is correct
27 Correct 238 ms 51672 KB Output is correct
28 Correct 428 ms 54352 KB Output is correct
29 Correct 349 ms 51428 KB Output is correct
30 Correct 409 ms 51188 KB Output is correct
31 Correct 457 ms 52812 KB Output is correct
32 Correct 229 ms 50048 KB Output is correct
33 Correct 461 ms 47312 KB Output is correct
34 Correct 321 ms 53380 KB Output is correct
35 Correct 269 ms 56432 KB Output is correct
36 Correct 375 ms 52156 KB Output is correct
37 Correct 446 ms 50124 KB Output is correct
38 Correct 66 ms 40136 KB Output is correct
39 Correct 103 ms 56804 KB Output is correct
40 Runtime error 21 ms 30156 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 9 ms 14420 KB Output is correct
2 Correct 20 ms 15012 KB Output is correct
3 Correct 15 ms 15080 KB Output is correct
4 Correct 12 ms 15060 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 13 ms 14932 KB Output is correct
9 Correct 14 ms 15060 KB Output is correct
10 Correct 11 ms 14484 KB Output is correct
11 Correct 10 ms 14420 KB Output is correct
12 Correct 248 ms 35264 KB Output is correct
13 Correct 497 ms 48864 KB Output is correct
14 Correct 567 ms 45356 KB Output is correct
15 Correct 671 ms 48648 KB Output is correct
16 Correct 717 ms 49208 KB Output is correct
17 Correct 368 ms 49220 KB Output is correct
18 Correct 8 ms 14292 KB Output is correct
19 Correct 234 ms 45580 KB Output is correct
20 Correct 8 ms 14392 KB Output is correct
21 Correct 95 ms 50204 KB Output is correct
22 Correct 105 ms 53768 KB Output is correct
23 Correct 124 ms 57040 KB Output is correct
24 Correct 123 ms 58340 KB Output is correct
25 Correct 10 ms 15060 KB Output is correct
26 Correct 11 ms 15136 KB Output is correct
27 Correct 10 ms 15188 KB Output is correct
28 Runtime error 21 ms 29092 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -