oj.uz

Submission #559297

# Submission time Handle Problem Language Result Execution time Memory
559297 2022-05-09T15:09:08 Z LastRonin Road Closures (APIO21_roads) C++14
22 / 100
 602 ms 58308 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);
	if(z.s == nullptr)exit(0);
	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:166: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]
  166 |     if(g2[u.f].size() > j) {
      |        ~~~~~~~~~~~~~~~^~~
roads.cpp:171: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]
  171 |     else if(g2[u.f].size() == j) {
      |             ~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 15 ms 15060 KB Output is correct
3 Correct 14 ms 15060 KB Output is correct
4 Correct 11 ms 15028 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14488 KB Output is correct
8 Correct 13 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 8 ms 14420 KB Output is correct
12 Correct 232 ms 35264 KB Output is correct
13 Correct 406 ms 48944 KB Output is correct
14 Correct 533 ms 45324 KB Output is correct
15 Correct 602 ms 48692 KB Output is correct
16 Correct 601 ms 49276 KB Output is correct
17 Correct 263 ms 49212 KB Output is correct
18 Correct 7 ms 14420 KB Output is correct
19 Correct 221 ms 45584 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 92 ms 50072 KB Output is correct
3 Correct 100 ms 53764 KB Output is correct
4 Correct 110 ms 57120 KB Output is correct
5 Correct 108 ms 58248 KB Output is correct
6 Correct 9 ms 15132 KB Output is correct
7 Correct 9 ms 15188 KB Output is correct
8 Correct 9 ms 15188 KB Output is correct
9 Runtime error 20 ms 29088 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 7 ms 14292 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 7 ms 14480 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Runtime error 22 ms 29260 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 7 ms 14292 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 7 ms 14480 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Runtime error 22 ms 29260 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 227 ms 52344 KB Output is correct
2 Correct 245 ms 51592 KB Output is correct
3 Correct 284 ms 57084 KB Output is correct
4 Correct 231 ms 53476 KB Output is correct
5 Correct 290 ms 57228 KB Output is correct
6 Correct 286 ms 55112 KB Output is correct
7 Correct 261 ms 55984 KB Output is correct
8 Correct 245 ms 46396 KB Output is correct
9 Correct 211 ms 54844 KB Output is correct
10 Correct 258 ms 53752 KB Output is correct
11 Correct 277 ms 54352 KB Output is correct
12 Correct 260 ms 52304 KB Output is correct
13 Correct 8 ms 14384 KB Output is correct
14 Correct 92 ms 53876 KB Output is correct
15 Correct 106 ms 58308 KB Output is correct
16 Correct 10 ms 15200 KB Output is correct
17 Correct 10 ms 15200 KB Output is correct
18 Correct 12 ms 15180 KB Output is correct
19 Correct 12 ms 15060 KB Output is correct
20 Correct 13 ms 15200 KB Output is correct
21 Correct 231 ms 45624 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 52344 KB Output is correct
2 Correct 245 ms 51592 KB Output is correct
3 Correct 284 ms 57084 KB Output is correct
4 Correct 231 ms 53476 KB Output is correct
5 Correct 290 ms 57228 KB Output is correct
6 Correct 286 ms 55112 KB Output is correct
7 Correct 261 ms 55984 KB Output is correct
8 Correct 245 ms 46396 KB Output is correct
9 Correct 211 ms 54844 KB Output is correct
10 Correct 258 ms 53752 KB Output is correct
11 Correct 277 ms 54352 KB Output is correct
12 Correct 260 ms 52304 KB Output is correct
13 Correct 8 ms 14384 KB Output is correct
14 Correct 92 ms 53876 KB Output is correct
15 Correct 106 ms 58308 KB Output is correct
16 Correct 10 ms 15200 KB Output is correct
17 Correct 10 ms 15200 KB Output is correct
18 Correct 12 ms 15180 KB Output is correct
19 Correct 12 ms 15060 KB Output is correct
20 Correct 13 ms 15200 KB Output is correct
21 Correct 231 ms 45624 KB Output is correct
22 Correct 9 ms 14420 KB Output is correct
23 Correct 8 ms 14292 KB Output is correct
24 Correct 9 ms 14316 KB Output is correct
25 Correct 192 ms 46604 KB Output is correct
26 Correct 162 ms 43196 KB Output is correct
27 Correct 234 ms 51644 KB Output is correct
28 Correct 428 ms 54360 KB Output is correct
29 Correct 376 ms 51328 KB Output is correct
30 Correct 416 ms 51140 KB Output is correct
31 Correct 468 ms 52604 KB Output is correct
32 Correct 270 ms 50064 KB Output is correct
33 Correct 446 ms 47036 KB Output is correct
34 Correct 368 ms 53452 KB Output is correct
35 Correct 282 ms 56228 KB Output is correct
36 Correct 410 ms 52208 KB Output is correct
37 Correct 462 ms 50084 KB Output is correct
38 Correct 83 ms 40140 KB Output is correct
39 Correct 123 ms 56708 KB Output is correct
40 Runtime error 25 ms 30144 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 15 ms 15060 KB Output is correct
3 Correct 14 ms 15060 KB Output is correct
4 Correct 11 ms 15028 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14488 KB Output is correct
8 Correct 13 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 8 ms 14420 KB Output is correct
12 Correct 232 ms 35264 KB Output is correct
13 Correct 406 ms 48944 KB Output is correct
14 Correct 533 ms 45324 KB Output is correct
15 Correct 602 ms 48692 KB Output is correct
16 Correct 601 ms 49276 KB Output is correct
17 Correct 263 ms 49212 KB Output is correct
18 Correct 7 ms 14420 KB Output is correct
19 Correct 221 ms 45584 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 92 ms 50072 KB Output is correct
22 Correct 100 ms 53764 KB Output is correct
23 Correct 110 ms 57120 KB Output is correct
24 Correct 108 ms 58248 KB Output is correct
25 Correct 9 ms 15132 KB Output is correct
26 Correct 9 ms 15188 KB Output is correct
27 Correct 9 ms 15188 KB Output is correct
28 Runtime error 20 ms 29088 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -