| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1228704 | CELD_07 | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
#include "closing.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<pair<ll, ll>>> adj;
inline void dfs(vector<ll>& dist, ll n, ll p){
for(auto& [x, y]: adj[n]){
if(x==p)continue;
dist[x]=dist[n]+y;
dfs(dist, x, 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){
if(X>Y)swap(X, Y);
vector<ll> dist(N+1, 0), dist1(N+1, 0);
vector<vector<pair<ll, ll>>>().swap(adj);
adj.resize(N+1);
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(dist, X, X);
dfs(dist1, Y, Y);
vector<ll> v2;
for(int i=0; i<N; i++){
v2.push_back(min(dist[i], dist1[i]));
}
sort(all(v2));
ll cnt=0, res=0;
for(int i=0; i<N; i++){
cnt+=v2[i];
if(cnt<=K)res=i+1;
}
for(int i=0; i<N; i++){
priority_queue<ll> pq;
cnt=0;
for(int j=i; j<N; j++){
cnt+=min(dist[j], dist1[j]);
while(!pq.empty() && cnt>K){cnt-=pq.top();pq.pop();}
ll o=max(dist[j], dist1[j])-min(dist[j], dist1[j]);
if(cnt+o<=K){cnt+=o;pq.push(o);}
else if(pq.top()>o){cnt-=pq.top();cnt+=o;pq.pop();pq.push(o);}
ll o1=pq.size();
if(i<=X && j>=Y)res=max(res, (j-i)+1+o1)
}
}
return res;
}