#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
#define int long long
const int MAXN = 3005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
vector<pi>adj[MAXN];
int par[MAXN];
int dep[MAXN];
void dfs(int x, int p){
par[x]=p;
for(auto v:adj[x])if(v.first!=p){
dep[v.first]=dep[x]+1;
dfs(v.first,x);
}
}
int dd[2][MAXN];
void bfs(int src, int xx){
queue<int> qu;
memset(dd[xx],-1,sizeof dd[xx]);
dd[xx][src]=0;
qu.push(src);
while(qu.size()){
int c=qu.front();
qu.pop();
for(auto v:adj[c]){
if(dd[xx][v.first] == -1 || dd[xx][v.first] > dd[xx][c]+v.second){
dd[xx][v.first]=dd[xx][c]+v.second;
qu.push(v.first);
}
}
}
}
int32_t max_score(int32_t n, int32_t X, int32_t Y, long long K,
std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
for(int i=0;i<n;i++){
adj[i].clear();
}
for(int i=0;i<n-1;i++){
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
}
dfs(1,-1);
vector<int> v1,v2;
int x=X,y=Y;
while(x!=y){
if(dep[x]>dep[y]){
v1.push_back(x);
x=par[x];
} else{
v2.push_back(y);
y=par[y];
}
}
unordered_set<int> path;
reverse(v2.begin(),v2.end());
vector<int> vec;
for(auto e:v1)vec.push_back(e);
vec.push_back(x);
for(auto e:v2)vec.push_back(e);
for(auto e:vec)path.insert(e);
int ans=2;
// 1. calc if there's 0 intersection--just greedily choose the cheapest node
bfs(X,0);
bfs(Y,1);
{
vector<int> vs;
for(int i=0;i<n;i++)vs.push_back(dd[0][i]);
for(int i=0;i<n;i++)vs.push_back(dd[1][i]);
sort(vs.begin(),vs.end());
int cst=0;
int cc=0;
for(auto x:vs){
cst+=x;
++cc;
if(cst<=K){
ans=max(ans,cc);
} else{
break;
}
}
}
// 2. if there's at least 1 intersection, it'll happen on the path
int cost = 0;
int cnt=0;
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> one; //{cost,index,min/max}
priority_queue<pi,vector<pi>,greater<pi>> both;
for(int k=0;k<n;k++){
both.push({max(dd[0][k],dd[1][k]),k});
one.push({min(dd[0][k],dd[1][k]),k,0});
}
set<pi>doneone;
set<int>doneboth;
while(true){
ans=max(ans,cnt);
// try taking 1 only
while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
if(one.size()){
if(cost+one.top()[0]<=K)ans=max(ans,cnt+1);
}
int c1=oo,c2=oo;
if(one.size()){
c1=0;
array<int,3> cur=one.top();
c1+=cur[0];
one.pop();
while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
if(one.size())c1+=one.top()[0];
else c1=oo;
one.push(cur);
}
while(both.size() && doneboth.find(both.top().second) != doneboth.end())both.pop();
if(both.size()){
c2=both.top().first;
}
if(c2==oo && c1==oo)break;
if(c2<c1){ // we should take the smaller one of the both
assert(both.size());
pi cur=both.top();
cnt++;
cost += min(dd[0][cur.second],dd[1][cur.second]);
one.push({abs(dd[0][cur.second]-dd[1][cur.second]),cur.second,1});
doneone.insert({cur.second,0});
both.pop();
} else{
array<int,3>cur=one.top();
one.pop();
cnt++;
cost+=cur[0];
if(cur[2] == 0){ // push max
one.push({max(dd[0][cur[1]],dd[1][cur[1]])-cur[0],cur[1],1});
doneboth.insert(cur[1]);
}
}
if(cost<=K){
ans=max(ans,cnt);
} else{
break;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
48 ms |
10160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
