#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#include <vector>
const ll NN = 2e5 + 5;
vector<pll> v[NN];
ll isi[NN], py[NN], te, ps[NN];
vector<ll> isi2;
void dfs(ll pos, ll par, ll now)
{
te++;
isi[te] = pos;
py[pos] = te;
ps[te] = now;
for(auto nx : v[pos])
{
if(nx.fi != par)
dfs(nx.fi, pos, now + nx.se);
}
}
void dfs2(ll pos, ll par, ll now)
{
isi2.pb(now);
for(auto nx : v[pos])
{
if(nx.fi != par)
dfs2(nx.fi, pos, now + nx.se);
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
cout << X << " " << Y << "_\n";
ll perlu = (X < Y);
te = 0;
ll R = 0;
for(ll i = 0; i < N; i++)
{
py[i] = 0;
isi[i + 1] = 0;
v[i].clear();
}
isi2.clear();
for(ll i = 0; i < V.size(); i++)
{
// cout << U[i] << " " << V[i] << " " << W[i] << "@\n";
v[U[i]].pb(mp(V[i], W[i]));
v[V[i]].pb(mp(U[i], W[i]));
}
for(ll i = 0; i < N; i++)
if(v[i].size() == 1)
{
R = i;
break;
}
dfs(R, R, 0);
dfs2(X, X, 0);
dfs2(Y, Y, 0);
ll now = K, ret = 0;
sort(isi2.begin(), isi2.end());
for(ll i = 0; i < 2 * N; i++)
{
if(isi2[i] > now)
break;
now -= isi2[i];
ret++;
}
// return ret;
if(py[X] > py[Y])
swap(X, Y);
// cout << py[X] << " " << py[Y] << " @\n";
for(ll i = py[X]; i <= py[Y]; i++)
{
ll sisa = K, now = 0;
for(ll j = py[X]; j <= i; j++)
{
now++;
sisa -= ps[j] - ps[py[X]];
}
for(ll j = i + 1; j <= py[Y]; j++)
{
now++;
sisa -= ps[py[Y]] - ps[j];
}
for(ll l = 1; l <= py[X]; l++)
{
vector<ll> cal;
ll sisa2 = sisa;
ll now2 = now;
// cout << now << "@\n";
for(ll j = l; j < py[X]; j++)
{
sisa2 -= ps[py[X]] - ps[j];
now2++;
cal.pb(ps[py[Y]] - ps[py[X]]); // Y
}
for(ll j = py[X]; j <= i; j++)
cal.pb(max(0LL, (ps[py[Y]] - ps[j]) - (ps[j] - ps[py[X]])));
for(ll j = py[Y] + 1; j <= N; j++)
cal.pb(ps[j] - ps[py[Y]]);
// cout << i << " " << l << "@\n";
// cout << cal.size() << " " << now2 << "_\n";
if(sisa2 < 0)
continue;
// cout << i << " " << now << " " << sisa << "_\n";
sort(cal.begin(), cal.end());
for(ll j = 0; j < cal.size(); j++)
{
if(cal[j] > sisa2)
break;
sisa2 -= cal[j];
now2++;
}
ret = max(ret, now2);
}
}
ll sisa = K;
now = 0;
for(ll i = py[X]; i <= py[Y]; i++)
{
sisa -= max(ps[py[Y]] - ps[i], ps[i] - ps[py[X]]);
now += 2;
}
for(ll l = 1; l <= py[X]; l++)
{
vector<ll> cal;
ll sisa2 = sisa;
ll now2 = now;
// cout << now << "@\n";
for(ll j = l; j < py[X]; j++)
{
sisa2 -= ps[py[X]] - ps[j];
now2++;
cal.pb(ps[py[Y]] - ps[py[X]]); // Y
}
for(ll j = py[Y] + 1; j <= N; j++)
cal.pb(ps[j] - ps[py[Y]]);
// cout << i << " " << l << "@\n";
// cout << cal.size() << " " << now2 << "_\n";
if(sisa2 < 0)
continue;
// cout << i << " " << now << " " << sisa << "_\n";
sort(cal.begin(), cal.end());
for(ll j = 0; j < cal.size(); j++)
{
if(cal[j] > sisa2)
break;
sisa2 -= cal[j];
now2++;
}
ret = max(ret, now2);
}
if(perlu)
return max((int)ret, max_score(N, Y, X, K, U, V, W));
else
return ret;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:51:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(ll i = 0; i < V.size(); i++)
| ~~^~~~~~~~~~
closing.cpp:119:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(ll j = 0; j < cal.size(); j++)
| ~~^~~~~~~~~~~~
closing.cpp:160:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(ll j = 0; j < cal.size(); j++)
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1038 ms |
33976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
