#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
ll dis[2][N];
ll tab[N][2];
int cnt[N];
bool vis[2][N], chk[2][N];
vector<pair<int, ll>> ed[N];
vector<int> pth;
inline void Clean(int n)
{
for(int i = 0; i < n; ++i)
{
ed[i].clear();
vis[0][i] = false; vis[1][i] = false;
chk[0][i] = false; chk[1][i] = false;
}
}
void DFSD(int v, int r)
{
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(dis[r][ed[v][i].st] <= dis[r][v]) continue;
dis[r][ed[v][i].st] = dis[r][v] + ed[v][i].nd;
DFSD(ed[v][i].st, r);
}
}
bool DFSP(int v, int tar, int o)
{
if(v == tar)
{
pth.pb(v); return true;
}
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(ed[v][i].st == o) continue;
if(DFSP(ed[v][i].st, tar, v))
{
pth.pb(v); return true;
}
}
return false;
}
int Norm(int n, int x, int y, ll k)
{
//cerr << "Norm: \n";
pth.clear();
int v, r, ans = 0;
priority_queue<pair<ll, pair<int, int>>> q;
q.push(make_pair(0, make_pair(x, 0)));
q.push(make_pair(0, make_pair(y, 1)));
//cerr << x << " " << y << "\n";
while((int)q.size() > 0 && -q.top().st <= k)
{
++ans;
ll xd = q.top().st;
v = q.top().nd.st; r = q.top().nd.nd;
q.pop();
if(vis[r][v]) continue;
k += xd;
//cerr << v << " " << r << " " << dis[r][v] << "\n";
vis[r][v] = true;
if(!vis[r ^ 1][v] && chk[r ^ 1][v]) q.push(make_pair(dis[r][v] - dis[r ^ 1][v], make_pair(v, r ^ 1)));
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[r][ed[v][i].st]) continue;
chk[r][ed[v][i].st] = true;
q.push(make_pair(-dis[r][ed[v][i].st], make_pair(ed[v][i].st, r)));
}
}
for(int i = 0; i < n; ++i)
{
vis[0][i] = false; vis[1][i] = false;
chk[0][i] = false; chk[1][i] = false;
}
return ans;
}
int PthA(int n, int x, int y, ll k)
{
//cerr << "Pth\n";
int ans, v;
ll val;
priority_queue<pair<ll, int>> q1, q2;
DFSP(x, y, 0);
for(int i = 0; i < n; ++i)
{
tab[i][0] = min(dis[0][i], dis[1][i]);
tab[i][1] = max(dis[0][i], dis[1][i]) - tab[i][0];
}
for(int i = 0; i < (int)pth.size(); ++i)
{
k -= min(dis[0][pth[i]], dis[1][pth[i]]);
++cnt[pth[i]];
}
if(k < 0LL) return 0;
ans = pth.size();
for(int i = 0; i < n; ++i)
{
if(cnt[i] == 0)
q2.push(make_pair(-tab[i][0] - tab[i][1], i));
q1.push(make_pair(-tab[i][cnt[i]], i));
}
ll cst = I;
while(k > 0 && (int)q1.size() > 0)
{
v = q1.top().nd;
val = -q1.top().st;
q1.pop();
while((int)q1.size() > 0 && cnt[q1.top().nd] > 1) q1.pop();
cst = I;
if((int)q1.size() == 0 || (int)q2.size() == 0 || -q2.top().st > k || -q1.top().st + val <= -q2.top().st)
{
if(val > k) break;
if((int)q2.size() > 0) cst = -q2.top().nd - val;
k -= val; ++ans;
++cnt[v];
if(cnt[v] < 2) q1.push(make_pair(-tab[v][1], v));
}else
{
q1.push(make_pair(-val, v));
v = q2.top().nd; val = -q2.top().st;
q2.pop();
cnt[v] = 2;
ans += 2;
k -= val;
}
while((int)q1.size() > 0 && cnt[q1.top().nd] > 1) q1.pop();
while((int)q2.size() > 0 && cnt[q2.top().nd] > 0) q2.pop();
}
if(cst <= k) ++ans;
return ans;
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
int n = N, u = X, v = Y, answer;
//cerr << "xd " << X << " " << Y << "\n";
for(int i = 0; i < n - 1; ++i)
{
ed[U[i]].pb(make_pair(V[i], W[i]));
ed[V[i]].pb(make_pair(U[i], W[i]));
}
for(int j = 0; j < 2; ++j)
for(int i = 0; i < n; ++i)
dis[j][i] = I;
dis[0][u] = 0LL; dis[1][v] = 0LL;
DFSD(u, 0); DFSD(v, 1);
//cerr << "xd\n";
answer = Norm(n, u, v, K);
answer = max(answer, PthA(n, u, v, K));
Clean(n);
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
34168 KB |
Output is correct |
| 2 |
Correct |
100 ms |
39368 KB |
Output is correct |
| 3 |
Correct |
47 ms |
9040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
