#include "closing.h"
#include <vector>
#include <queue>
#include <array>
#include <algorithm>
#include <iostream>
#define ll long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template <typename T>
void dbg_vec(string str, vector <T> &x) {
cerr << "DBG " << str << '\n';
for (int i = 0; i < sz(x); ++i) {
cerr << "I " << i << " -> " << x[i] << '\n';
}
cerr << '\n';
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
vector <vector <array <int, 2> > > g (N);
for (int i = 0; i < N - 1; ++i) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
auto bfs = [&] (int source) -> vector <ll> {
vector <ll> dist (N, -1);
queue <int> coda;
dist[source] = 0;
coda.push(source);
while (!coda.empty()) {
int node = coda.front();
coda.pop();
for (auto [to, w] : g[node]) {
if (dist[to] == -1) {
dist[to] = dist[node] + w;
coda.push(to);
}
}
}
return dist;
};
vector <ll> dist_x = bfs(X);
vector <ll> dist_y = bfs(Y);
// dbg_vec("dist_x", dist_x);
// dbg_vec("dist_y", dist_y);
vector <pair <ll, int> > dist_node;
for (int i = 0; i < N; ++i) {
dist_node.push_back({dist_x[i], i});
dist_node.push_back({dist_y[i], i});
}
sort(all(dist_node));
vector <ll> dist (N);
ll sum = 0;
for (auto [d, node] : dist_node) {
ll diff = d - dist[node];
if (sum + diff <= K) {
dist[node] = d;
sum += diff;
} else { // non posso piu' aggiungere delle distanze
break;
}
}
int ans = 0;
// dbg_vec("dist", dist);
for (int node = 0; node < N; ++node) {
if (dist_x[node] <= dist[node]) {
// cerr << "Aumemnto X " << node << " " << dist[node] << " " << dist_x[node] << '\n';
++ans;
}
if (dist_y[node] <= dist[node]) {
// cerr << "Aumemnto Y " << node << " " << dist[node] << " " << dist_y[node] << '\n';
++ans;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
28732 KB |
Output is correct |
2 |
Correct |
127 ms |
28092 KB |
Output is correct |
3 |
Correct |
83 ms |
2888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
228 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
228 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
228 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
228 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
228 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
228 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
228 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
228 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '96', found: '93' |
8 |
Halted |
0 ms |
0 KB |
- |