#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const long long INF = 1e18;
int onp[maxn];
long long depX[maxn], depY[maxn];
vector<pair<int, int>> g[maxn];
void dfsX(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depX[v.first] = depX[x] + v.second;
dfsX(v.first, x);
}
}
void dfsY(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depY[v.first] = depY[x] + v.second;
dfsY(v.first, x);
}
}
long long solve1(int n, long long k)
{
vector<long long> vec;
vec.insert(vec.end(), depX, depX + n);
vec.insert(vec.end(), depY, depY + n);
sort(vec.begin(), vec.end());
long long crr = 0;
for (int i = 0; i < vec.size(); i++)
{
crr += vec[i];
if (crr > k)
return i;
}
return vec.size();
}
vector<int> path;
bool dfs_path(int x, int endp, int p = -1)
{
if (x == endp)
return (onp[x] = true);
for (auto v : g[x])
{
if (v.first == p)
continue;
onp[x] |= dfs_path(v.first, endp, x);
}
return onp[x];
}
vector<long long> vec1, vec2;
vector<long long> knapsack[maxn];
int mark[maxn];
bool chk(pair<int, int> a)
{
return a.second < mark[a.first];
}
long long tval(pair<int, int> a)
{
if (chk(a))
return knapsack[a.first][a.second];
else
return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}
long long eval(pair<int, int> a)
{
if (chk(a))
return knapsack[a.first][a.second] * 2;
else
return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}
int nxt(pair<int, int> a)
{
if (chk(a))
return a.second + 1;
else
return a.second + 2;
}
void dfs_gen(int x, int p, long long cnst)
{
long long val;
if (p == -1)
val = 0;
else
val = min(depX[x], depY[x]);
if (val > cnst)
vec2.push_back(val);
else
vec1.push_back(val);
for (auto v : g[x])
{
if (v.first == p || onp[v.first])
continue;
dfs_gen(v.first, x, cnst);
}
}
struct cmp
{
bool operator()(const pair<int, int> a, const pair<int, int> b) const
{
return eval(a) > eval(b);
}
};
long long solve2(int n, long long k, int x, int y)
{
dfs_path(x, y);
int len = 0;
for (int i = 0; i < n; i++)
{
if (onp[i])
{
k -= min(depX[i], depY[i]);
vec1.clear();
vec2.clear();
long long inc = abs(depX[i] - depY[i]);
dfs_gen(i, -1, inc);
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
knapsack[len] = vec1;
for (auto v : vec1)
knapsack[len].push_back(inc);
mark[len] = knapsack[len].size();
for (auto v : vec2)
{
knapsack[len].push_back(v);
knapsack[len].push_back(inc);
}
len++;
// cout << i << endl;
// for(auto v: knapsack[len])cout << v << " ";
// cout << endl;
}
}
// cout << "left " << k << endl;
if (k < 0)
return 0;
long long re = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
for (int i = 0; i < len; i++)
pq.push({i, 0});
while (!pq.empty())
{
auto x = pq.top();
// cout << "pq " << x.first << " " << x.second << endl;
pq.pop();
if (tval(x) <= k)
{
k -= tval(x);
re += !chk(x) + 1;
if (nxt(x) < knapsack[x.first].size())
pq.push({x.first, nxt(x)});
}
else
{
if (knapsack[x.first][x.second] <= k)
{
re++;
break;
}
}
}
return re;
}
void reset(int n)
{
for (int i = 0; i < n; i++)
{
g[i].clear();
onp[i] = 0;
}
path.clear();
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
reset(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]});
}
depX[X] = 0;
depY[Y] = 0;
dfsX(X);
dfsY(Y);
long long ans = max(solve1(N, K), solve2(N, K, X, Y));
return ans;
}
Compilation message
closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < vec.size(); i++)
| ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:142:23: warning: unused variable 'v' [-Wunused-variable]
142 | for (auto v : vec1)
| ^
closing.cpp:172:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if (nxt(x) < knapsack[x.first].size())
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
40396 KB |
Output is correct |
2 |
Correct |
178 ms |
47356 KB |
Output is correct |
3 |
Correct |
74 ms |
12484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9696 KB |
Output is correct |
13 |
Correct |
4 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
4 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
4 ms |
9684 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
4 ms |
9812 KB |
Output is correct |
24 |
Correct |
4 ms |
9812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9696 KB |
Output is correct |
13 |
Correct |
4 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
4 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
4 ms |
9684 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
4 ms |
9812 KB |
Output is correct |
24 |
Correct |
4 ms |
9812 KB |
Output is correct |
25 |
Correct |
6 ms |
9684 KB |
Output is correct |
26 |
Correct |
5 ms |
10196 KB |
Output is correct |
27 |
Correct |
5 ms |
10196 KB |
Output is correct |
28 |
Correct |
6 ms |
10196 KB |
Output is correct |
29 |
Correct |
6 ms |
10196 KB |
Output is correct |
30 |
Correct |
5 ms |
10196 KB |
Output is correct |
31 |
Correct |
6 ms |
10324 KB |
Output is correct |
32 |
Correct |
6 ms |
10324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Incorrect |
4 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '9', found: '8' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
4 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9696 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
4 ms |
9684 KB |
Output is correct |
21 |
Incorrect |
4 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '9', found: '8' |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
4 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9696 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
4 ms |
9684 KB |
Output is correct |
20 |
Correct |
4 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
4 ms |
9684 KB |
Output is correct |
24 |
Correct |
4 ms |
9812 KB |
Output is correct |
25 |
Correct |
4 ms |
9812 KB |
Output is correct |
26 |
Correct |
5 ms |
9684 KB |
Output is correct |
27 |
Correct |
4 ms |
9684 KB |
Output is correct |
28 |
Incorrect |
4 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '9', found: '8' |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
4 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9696 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
4 ms |
9684 KB |
Output is correct |
20 |
Correct |
4 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
4 ms |
9684 KB |
Output is correct |
24 |
Correct |
4 ms |
9812 KB |
Output is correct |
25 |
Correct |
4 ms |
9812 KB |
Output is correct |
26 |
Correct |
6 ms |
9684 KB |
Output is correct |
27 |
Correct |
5 ms |
10196 KB |
Output is correct |
28 |
Correct |
5 ms |
10196 KB |
Output is correct |
29 |
Correct |
6 ms |
10196 KB |
Output is correct |
30 |
Correct |
6 ms |
10196 KB |
Output is correct |
31 |
Correct |
5 ms |
10196 KB |
Output is correct |
32 |
Correct |
6 ms |
10324 KB |
Output is correct |
33 |
Correct |
6 ms |
10324 KB |
Output is correct |
34 |
Correct |
5 ms |
9684 KB |
Output is correct |
35 |
Correct |
4 ms |
9684 KB |
Output is correct |
36 |
Incorrect |
4 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '9', found: '8' |
37 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
4 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
4 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9696 KB |
Output is correct |
14 |
Correct |
4 ms |
9684 KB |
Output is correct |
15 |
Correct |
4 ms |
9684 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
4 ms |
9684 KB |
Output is correct |
18 |
Correct |
4 ms |
9684 KB |
Output is correct |
19 |
Correct |
4 ms |
9684 KB |
Output is correct |
20 |
Correct |
4 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
4 ms |
9684 KB |
Output is correct |
23 |
Correct |
4 ms |
9684 KB |
Output is correct |
24 |
Correct |
4 ms |
9812 KB |
Output is correct |
25 |
Correct |
4 ms |
9812 KB |
Output is correct |
26 |
Correct |
6 ms |
9684 KB |
Output is correct |
27 |
Correct |
5 ms |
10196 KB |
Output is correct |
28 |
Correct |
5 ms |
10196 KB |
Output is correct |
29 |
Correct |
6 ms |
10196 KB |
Output is correct |
30 |
Correct |
6 ms |
10196 KB |
Output is correct |
31 |
Correct |
5 ms |
10196 KB |
Output is correct |
32 |
Correct |
6 ms |
10324 KB |
Output is correct |
33 |
Correct |
6 ms |
10324 KB |
Output is correct |
34 |
Correct |
5 ms |
9684 KB |
Output is correct |
35 |
Correct |
4 ms |
9684 KB |
Output is correct |
36 |
Incorrect |
4 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '9', found: '8' |
37 |
Halted |
0 ms |
0 KB |
- |