oj.uz

Submission #559308

# Submission time Handle Problem Language Result Execution time Memory
559308 2022-05-09T15:14:09 Z LastRonin Road Closures (APIO21_roads) C++11
22 / 100
 890 ms 58332 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(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 8 ms 14292 KB Output is correct
2 Correct 16 ms 15080 KB Output is correct
3 Correct 19 ms 15132 KB Output is correct
4 Correct 17 ms 15104 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 9 ms 14488 KB Output is correct
7 Correct 10 ms 14420 KB Output is correct
8 Correct 29 ms 14924 KB Output is correct
9 Correct 29 ms 15060 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 293 ms 35176 KB Output is correct
13 Correct 515 ms 48972 KB Output is correct
14 Correct 681 ms 45296 KB Output is correct
15 Correct 835 ms 48708 KB Output is correct
16 Correct 890 ms 49276 KB Output is correct
17 Correct 321 ms 49256 KB Output is correct
18 Correct 9 ms 14292 KB Output is correct
19 Correct 281 ms 45644 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14380 KB Output is correct
2 Correct 103 ms 50068 KB Output is correct
3 Correct 121 ms 53772 KB Output is correct
4 Correct 119 ms 56996 KB Output is correct
5 Correct 132 ms 58236 KB Output is correct
6 Correct 11 ms 15136 KB Output is correct
7 Correct 10 ms 15188 KB Output is correct
8 Correct 15 ms 15188 KB Output is correct
9 Runtime error 30 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 14292 KB Output is correct
2 Correct 12 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 11 ms 14420 KB Output is correct
6 Runtime error 20 ms 29140 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 14292 KB Output is correct
2 Correct 12 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 11 ms 14420 KB Output is correct
6 Runtime error 20 ms 29140 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 283 ms 52304 KB Output is correct
2 Correct 266 ms 51648 KB Output is correct
3 Correct 322 ms 57020 KB Output is correct
4 Correct 261 ms 53552 KB Output is correct
5 Correct 309 ms 57128 KB Output is correct
6 Correct 300 ms 55184 KB Output is correct
7 Correct 303 ms 55988 KB Output is correct
8 Correct 259 ms 46208 KB Output is correct
9 Correct 263 ms 54932 KB Output is correct
10 Correct 283 ms 53728 KB Output is correct
11 Correct 311 ms 54424 KB Output is correct
12 Correct 297 ms 52156 KB Output is correct
13 Correct 8 ms 14368 KB Output is correct
14 Correct 99 ms 53996 KB Output is correct
15 Correct 121 ms 58332 KB Output is correct
16 Correct 11 ms 15108 KB Output is correct
17 Correct 11 ms 15128 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 12 ms 15068 KB Output is correct
20 Correct 11 ms 15188 KB Output is correct
21 Correct 256 ms 45700 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 52304 KB Output is correct
2 Correct 266 ms 51648 KB Output is correct
3 Correct 322 ms 57020 KB Output is correct
4 Correct 261 ms 53552 KB Output is correct
5 Correct 309 ms 57128 KB Output is correct
6 Correct 300 ms 55184 KB Output is correct
7 Correct 303 ms 55988 KB Output is correct
8 Correct 259 ms 46208 KB Output is correct
9 Correct 263 ms 54932 KB Output is correct
10 Correct 283 ms 53728 KB Output is correct
11 Correct 311 ms 54424 KB Output is correct
12 Correct 297 ms 52156 KB Output is correct
13 Correct 8 ms 14368 KB Output is correct
14 Correct 99 ms 53996 KB Output is correct
15 Correct 121 ms 58332 KB Output is correct
16 Correct 11 ms 15108 KB Output is correct
17 Correct 11 ms 15128 KB Output is correct
18 Correct 12 ms 15188 KB Output is correct
19 Correct 12 ms 15068 KB Output is correct
20 Correct 11 ms 15188 KB Output is correct
21 Correct 256 ms 45700 KB Output is correct
22 Correct 8 ms 14292 KB Output is correct
23 Correct 8 ms 14312 KB Output is correct
24 Correct 8 ms 14292 KB Output is correct
25 Correct 222 ms 46640 KB Output is correct
26 Correct 167 ms 43204 KB Output is correct
27 Correct 233 ms 51720 KB Output is correct
28 Correct 448 ms 54360 KB Output is correct
29 Correct 341 ms 51456 KB Output is correct
30 Correct 409 ms 51180 KB Output is correct
31 Correct 459 ms 52688 KB Output is correct
32 Correct 219 ms 50044 KB Output is correct
33 Correct 391 ms 47124 KB Output is correct
34 Correct 316 ms 53428 KB Output is correct
35 Correct 238 ms 56244 KB Output is correct
36 Correct 381 ms 52176 KB Output is correct
37 Correct 405 ms 50104 KB Output is correct
38 Correct 66 ms 40132 KB Output is correct
39 Correct 104 ms 56712 KB Output is correct
40 Runtime error 22 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 8 ms 14292 KB Output is correct
2 Correct 16 ms 15080 KB Output is correct
3 Correct 19 ms 15132 KB Output is correct
4 Correct 17 ms 15104 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 9 ms 14488 KB Output is correct
7 Correct 10 ms 14420 KB Output is correct
8 Correct 29 ms 14924 KB Output is correct
9 Correct 29 ms 15060 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 293 ms 35176 KB Output is correct
13 Correct 515 ms 48972 KB Output is correct
14 Correct 681 ms 45296 KB Output is correct
15 Correct 835 ms 48708 KB Output is correct
16 Correct 890 ms 49276 KB Output is correct
17 Correct 321 ms 49256 KB Output is correct
18 Correct 9 ms 14292 KB Output is correct
19 Correct 281 ms 45644 KB Output is correct
20 Correct 12 ms 14380 KB Output is correct
21 Correct 103 ms 50068 KB Output is correct
22 Correct 121 ms 53772 KB Output is correct
23 Correct 119 ms 56996 KB Output is correct
24 Correct 132 ms 58236 KB Output is correct
25 Correct 11 ms 15136 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 15 ms 15188 KB Output is correct
28 Runtime error 30 ms 29140 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -