oj.uz

답안 #559282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559282 2022-05-09T15:01:03 Z LastRonin 도로 폐쇄 (APIO21_roads) C++14
22 / 100
 689 ms 65384 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 = 3e5 + 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 = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 22 ms 22228 KB Output is correct
3 Correct 18 ms 22064 KB Output is correct
4 Correct 17 ms 22100 KB Output is correct
5 Correct 13 ms 21460 KB Output is correct
6 Correct 13 ms 21460 KB Output is correct
7 Correct 13 ms 21460 KB Output is correct
8 Correct 17 ms 21980 KB Output is correct
9 Correct 19 ms 22088 KB Output is correct
10 Correct 14 ms 21556 KB Output is correct
11 Correct 14 ms 21548 KB Output is correct
12 Correct 244 ms 42264 KB Output is correct
13 Correct 438 ms 56012 KB Output is correct
14 Correct 579 ms 52564 KB Output is correct
15 Correct 678 ms 55752 KB Output is correct
16 Correct 689 ms 56252 KB Output is correct
17 Correct 311 ms 56320 KB Output is correct
18 Correct 12 ms 21460 KB Output is correct
19 Correct 237 ms 52676 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21384 KB Output is correct
2 Correct 116 ms 57080 KB Output is correct
3 Correct 116 ms 60824 KB Output is correct
4 Correct 124 ms 64052 KB Output is correct
5 Correct 119 ms 65384 KB Output is correct
6 Correct 15 ms 22100 KB Output is correct
7 Correct 14 ms 22300 KB Output is correct
8 Correct 14 ms 22172 KB Output is correct
9 Runtime error 32 ms 43484 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21456 KB Output is correct
2 Correct 15 ms 21460 KB Output is correct
3 Correct 12 ms 21436 KB Output is correct
4 Correct 14 ms 21520 KB Output is correct
5 Correct 12 ms 21540 KB Output is correct
6 Runtime error 32 ms 43464 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21456 KB Output is correct
2 Correct 15 ms 21460 KB Output is correct
3 Correct 12 ms 21436 KB Output is correct
4 Correct 14 ms 21520 KB Output is correct
5 Correct 12 ms 21540 KB Output is correct
6 Runtime error 32 ms 43464 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 59340 KB Output is correct
2 Correct 273 ms 58592 KB Output is correct
3 Correct 298 ms 64244 KB Output is correct
4 Correct 279 ms 60616 KB Output is correct
5 Correct 291 ms 64300 KB Output is correct
6 Correct 332 ms 62112 KB Output is correct
7 Correct 279 ms 63228 KB Output is correct
8 Correct 260 ms 53276 KB Output is correct
9 Correct 269 ms 61916 KB Output is correct
10 Correct 271 ms 60800 KB Output is correct
11 Correct 301 ms 61408 KB Output is correct
12 Correct 279 ms 59348 KB Output is correct
13 Correct 12 ms 21372 KB Output is correct
14 Correct 111 ms 60996 KB Output is correct
15 Correct 139 ms 65348 KB Output is correct
16 Correct 16 ms 22240 KB Output is correct
17 Correct 15 ms 22212 KB Output is correct
18 Correct 15 ms 22280 KB Output is correct
19 Correct 16 ms 22220 KB Output is correct
20 Correct 17 ms 22204 KB Output is correct
21 Correct 283 ms 52804 KB Output is correct

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 59340 KB Output is correct
2 Correct 273 ms 58592 KB Output is correct
3 Correct 298 ms 64244 KB Output is correct
4 Correct 279 ms 60616 KB Output is correct
5 Correct 291 ms 64300 KB Output is correct
6 Correct 332 ms 62112 KB Output is correct
7 Correct 279 ms 63228 KB Output is correct
8 Correct 260 ms 53276 KB Output is correct
9 Correct 269 ms 61916 KB Output is correct
10 Correct 271 ms 60800 KB Output is correct
11 Correct 301 ms 61408 KB Output is correct
12 Correct 279 ms 59348 KB Output is correct
13 Correct 12 ms 21372 KB Output is correct
14 Correct 111 ms 60996 KB Output is correct
15 Correct 139 ms 65348 KB Output is correct
16 Correct 16 ms 22240 KB Output is correct
17 Correct 15 ms 22212 KB Output is correct
18 Correct 15 ms 22280 KB Output is correct
19 Correct 16 ms 22220 KB Output is correct
20 Correct 17 ms 22204 KB Output is correct
21 Correct 283 ms 52804 KB Output is correct
22 Correct 15 ms 21460 KB Output is correct
23 Correct 12 ms 21356 KB Output is correct
24 Correct 13 ms 21456 KB Output is correct
25 Correct 211 ms 53676 KB Output is correct
26 Correct 216 ms 50348 KB Output is correct
27 Correct 265 ms 58708 KB Output is correct
28 Correct 485 ms 61412 KB Output is correct
29 Correct 360 ms 58488 KB Output is correct
30 Correct 416 ms 58172 KB Output is correct
31 Correct 460 ms 59756 KB Output is correct
32 Correct 267 ms 57116 KB Output is correct
33 Correct 411 ms 53976 KB Output is correct
34 Correct 368 ms 60436 KB Output is correct
35 Correct 252 ms 63416 KB Output is correct
36 Correct 415 ms 59300 KB Output is correct
37 Correct 504 ms 57140 KB Output is correct
38 Correct 81 ms 47304 KB Output is correct
39 Correct 112 ms 63824 KB Output is correct
40 Runtime error 42 ms 44492 KB Execution killed with signal 6
41 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 22 ms 22228 KB Output is correct
3 Correct 18 ms 22064 KB Output is correct
4 Correct 17 ms 22100 KB Output is correct
5 Correct 13 ms 21460 KB Output is correct
6 Correct 13 ms 21460 KB Output is correct
7 Correct 13 ms 21460 KB Output is correct
8 Correct 17 ms 21980 KB Output is correct
9 Correct 19 ms 22088 KB Output is correct
10 Correct 14 ms 21556 KB Output is correct
11 Correct 14 ms 21548 KB Output is correct
12 Correct 244 ms 42264 KB Output is correct
13 Correct 438 ms 56012 KB Output is correct
14 Correct 579 ms 52564 KB Output is correct
15 Correct 678 ms 55752 KB Output is correct
16 Correct 689 ms 56252 KB Output is correct
17 Correct 311 ms 56320 KB Output is correct
18 Correct 12 ms 21460 KB Output is correct
19 Correct 237 ms 52676 KB Output is correct
20 Correct 12 ms 21384 KB Output is correct
21 Correct 116 ms 57080 KB Output is correct
22 Correct 116 ms 60824 KB Output is correct
23 Correct 124 ms 64052 KB Output is correct
24 Correct 119 ms 65384 KB Output is correct
25 Correct 15 ms 22100 KB Output is correct
26 Correct 14 ms 22300 KB Output is correct
27 Correct 14 ms 22172 KB Output is correct
28 Runtime error 32 ms 43484 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -