Submission #1228705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228705		CELD_07	Closing Time (IOI23_closing)	C++20	0 / 100	1094 ms	28096 KiB

closing

#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.empty() && 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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17