oj.uz

Submission #559291

# Submission time Handle Problem Language Result Execution time Memory
559291 2022-05-09T15:05:36 Z LastRonin Road Closures (APIO21_roads) C++14
22 / 100
 661 ms 51280 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 = 1e5 + 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 = 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 4 ms 7252 KB Output is correct
2 Correct 9 ms 8020 KB Output is correct
3 Correct 11 ms 8020 KB Output is correct
4 Correct 7 ms 8020 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 8 ms 7892 KB Output is correct
9 Correct 10 ms 8020 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 227 ms 28156 KB Output is correct
13 Correct 400 ms 41920 KB Output is correct
14 Correct 549 ms 38336 KB Output is correct
15 Correct 661 ms 41748 KB Output is correct
16 Correct 575 ms 42236 KB Output is correct
17 Correct 262 ms 42116 KB Output is correct
18 Correct 3 ms 7252 KB Output is correct
19 Correct 221 ms 38596 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 99 ms 42972 KB Output is correct
3 Correct 106 ms 46720 KB Output is correct
4 Correct 111 ms 50044 KB Output is correct
5 Correct 109 ms 51280 KB Output is correct
6 Correct 6 ms 8020 KB Output is correct
7 Correct 6 ms 8208 KB Output is correct
8 Correct 6 ms 8152 KB Output is correct
9 Runtime error 11 ms 14876 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 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Runtime error 16 ms 14940 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 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Runtime error 16 ms 14940 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 264 ms 45260 KB Output is correct
2 Correct 284 ms 44536 KB Output is correct
3 Correct 321 ms 50020 KB Output is correct
4 Correct 258 ms 46436 KB Output is correct
5 Correct 290 ms 50056 KB Output is correct
6 Correct 290 ms 48132 KB Output is correct
7 Correct 330 ms 48832 KB Output is correct
8 Correct 271 ms 39156 KB Output is correct
9 Correct 282 ms 47876 KB Output is correct
10 Correct 291 ms 46700 KB Output is correct
11 Correct 340 ms 47412 KB Output is correct
12 Correct 353 ms 45008 KB Output is correct
13 Correct 6 ms 7252 KB Output is correct
14 Correct 109 ms 46928 KB Output is correct
15 Correct 109 ms 51216 KB Output is correct
16 Correct 8 ms 8148 KB Output is correct
17 Correct 8 ms 8148 KB Output is correct
18 Correct 9 ms 8088 KB Output is correct
19 Correct 15 ms 8128 KB Output is correct
20 Correct 8 ms 8148 KB Output is correct
21 Correct 245 ms 38532 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 45260 KB Output is correct
2 Correct 284 ms 44536 KB Output is correct
3 Correct 321 ms 50020 KB Output is correct
4 Correct 258 ms 46436 KB Output is correct
5 Correct 290 ms 50056 KB Output is correct
6 Correct 290 ms 48132 KB Output is correct
7 Correct 330 ms 48832 KB Output is correct
8 Correct 271 ms 39156 KB Output is correct
9 Correct 282 ms 47876 KB Output is correct
10 Correct 291 ms 46700 KB Output is correct
11 Correct 340 ms 47412 KB Output is correct
12 Correct 353 ms 45008 KB Output is correct
13 Correct 6 ms 7252 KB Output is correct
14 Correct 109 ms 46928 KB Output is correct
15 Correct 109 ms 51216 KB Output is correct
16 Correct 8 ms 8148 KB Output is correct
17 Correct 8 ms 8148 KB Output is correct
18 Correct 9 ms 8088 KB Output is correct
19 Correct 15 ms 8128 KB Output is correct
20 Correct 8 ms 8148 KB Output is correct
21 Correct 245 ms 38532 KB Output is correct
22 Correct 4 ms 7252 KB Output is correct
23 Correct 4 ms 7252 KB Output is correct
24 Correct 5 ms 7256 KB Output is correct
25 Correct 223 ms 39632 KB Output is correct
26 Correct 196 ms 36152 KB Output is correct
27 Correct 263 ms 44628 KB Output is correct
28 Correct 456 ms 47320 KB Output is correct
29 Correct 361 ms 44348 KB Output is correct
30 Correct 420 ms 44076 KB Output is correct
31 Correct 476 ms 45616 KB Output is correct
32 Correct 261 ms 42952 KB Output is correct
33 Correct 426 ms 39992 KB Output is correct
34 Correct 347 ms 46376 KB Output is correct
35 Correct 287 ms 49236 KB Output is correct
36 Correct 415 ms 45136 KB Output is correct
37 Correct 438 ms 43076 KB Output is correct
38 Correct 71 ms 33156 KB Output is correct
39 Correct 114 ms 49736 KB Output is correct
40 Runtime error 13 ms 15988 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 4 ms 7252 KB Output is correct
2 Correct 9 ms 8020 KB Output is correct
3 Correct 11 ms 8020 KB Output is correct
4 Correct 7 ms 8020 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 8 ms 7892 KB Output is correct
9 Correct 10 ms 8020 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 227 ms 28156 KB Output is correct
13 Correct 400 ms 41920 KB Output is correct
14 Correct 549 ms 38336 KB Output is correct
15 Correct 661 ms 41748 KB Output is correct
16 Correct 575 ms 42236 KB Output is correct
17 Correct 262 ms 42116 KB Output is correct
18 Correct 3 ms 7252 KB Output is correct
19 Correct 221 ms 38596 KB Output is correct
20 Correct 4 ms 7252 KB Output is correct
21 Correct 99 ms 42972 KB Output is correct
22 Correct 106 ms 46720 KB Output is correct
23 Correct 111 ms 50044 KB Output is correct
24 Correct 109 ms 51280 KB Output is correct
25 Correct 6 ms 8020 KB Output is correct
26 Correct 6 ms 8208 KB Output is correct
27 Correct 6 ms 8152 KB Output is correct
28 Runtime error 11 ms 14876 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -