oj.uz

Submission #559771

# Submission time Handle Problem Language Result Execution time Memory
559771 2022-05-10T14:42:46 Z flappybird Road Closures (APIO21_roads) C++17
5 / 100
 778 ms 53248 KB 
#include "roads.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 101010

int N;

vector<pii> adj[MAX];
int w[MAX];

typedef multiset<ll, greater<ll>> msl;
msl maxSet[MAX], st[MAX];
ll X[MAX];
int prt[MAX];
int K;
int deg[MAX];
ll sum;

void getW(int x, int p = -1) {
	prt[x] = p;
	for (auto& [v, c] : adj[x]) {
		if (v == p) continue;
		X[v] = w[v] = c;
		maxSet[x].insert(X[v]);
		sum += X[v];
		getW(v, x);
	}
}

bool exist(msl& ms, ll v) {
	return ms.find(v) != ms.end();
}

void refresh(int v) {
	while (st[v].size() && (*st[v].begin()) > *maxSet[v].rbegin()) {
		int x = *st[v].begin();
		int y = *maxSet[v].rbegin();
		sum -= y;
		sum += x;
		st[v].erase(st[v].find(x));
		maxSet[v].erase(maxSet[v].find(y));
		maxSet[v].insert(x);
		st[v].insert(y);
	}
}

void changev(int v, ll prv, ll nxt) {
	if (exist(maxSet[v], prv)) {
		maxSet[v].erase(maxSet[v].find(prv));
		maxSet[v].insert(nxt);
		sum -= prv;
		sum += nxt;
	}
	else {
		st[v].erase(maxSet[v].find(prv));
		st[v].insert(nxt);
	}
	refresh(v);
}

ll getK(int v) {
	if (maxSet[v].size() < K) return 0;
	return *maxSet[v].rbegin();
}

void calc(int v) {
	ll prevX = X[v];
	refresh(v);
	while (maxSet[v].size() > K) {
		st[v].insert(*maxSet[v].rbegin());
		int x = *maxSet[v].rbegin();
		maxSet[v].erase(maxSet[v].find(x));
		sum -= x;
	}
	X[v] = w[v] - getK(v);
	if (X[v] == prevX) return;
	if (!v) return;
	changev(prt[v], prevX, X[v]);
	calc(prt[v]);
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	::N = N;
	int i;
	ll sumW = 0;
	for (i = 0; i < N - 1; i++) adj[U[i]].emplace_back(V[i], W[i]), adj[V[i]].emplace_back(U[i], W[i]), sumW += W[i], deg[U[i]]++, deg[V[i]]++;
	getW(0);
	vector<int> degSort;
	for (i = 0; i < N; i++) degSort.push_back(i);
	sort(degSort.begin(), degSort.end(), [&](int i, int j) { return deg[i] > deg[j]; });
	vector<ll> ans(N);
	ans[N - 1] = sum;
	vector<int> changeList;
	int ptr = 0;
	for (K = N - 2; K >= 1; K--) {
		while (ptr < N && K < deg[degSort[ptr]]) changeList.push_back(degSort[ptr++]);
		for (auto v : changeList) calc(v);
		ans[K] = sum;
	}
	for (auto& v : ans) v = sumW - v;
	return ans;
}

Compilation message

roads.cpp: In function 'll getK(int)':
roads.cpp:65:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |  if (maxSet[v].size() < K) return 0;
      |      ~~~~~~~~~~~~~~~~~^~~
roads.cpp: In function 'void calc(int)':
roads.cpp:72:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  while (maxSet[v].size() > K) {
      |         ~~~~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 9 ms 12488 KB Output is correct
3 Correct 9 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 7 ms 12176 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12368 KB Output is correct
9 Correct 9 ms 12500 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 8 ms 12176 KB Output is correct
12 Correct 61 ms 21468 KB Output is correct
13 Correct 121 ms 27740 KB Output is correct
14 Correct 121 ms 26764 KB Output is correct
15 Correct 112 ms 28288 KB Output is correct
16 Correct 120 ms 28552 KB Output is correct
17 Correct 109 ms 28608 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 104 ms 26304 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Incorrect 778 ms 30912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 6 ms 12176 KB Output is correct
4 Runtime error 15 ms 24532 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 6 ms 12176 KB Output is correct
4 Runtime error 15 ms 24532 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 53248 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 53248 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 9 ms 12488 KB Output is correct
3 Correct 9 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 7 ms 12176 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12368 KB Output is correct
9 Correct 9 ms 12500 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 8 ms 12176 KB Output is correct
12 Correct 61 ms 21468 KB Output is correct
13 Correct 121 ms 27740 KB Output is correct
14 Correct 121 ms 26764 KB Output is correct
15 Correct 112 ms 28288 KB Output is correct
16 Correct 120 ms 28552 KB Output is correct
17 Correct 109 ms 28608 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 104 ms 26304 KB Output is correct
20 Correct 6 ms 12112 KB Output is correct
21 Incorrect 778 ms 30912 KB Output isn't correct
22 Halted 0 ms 0 KB -