Submission #1007072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007072		Abito	Closing Time (IOI23_closing)	C++17	0 / 100	66 ms	40684 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back
#define ppb pop_back
using namespace std;
const int N=6005;
int n,dis[2][N],dp[N][N],k;
vector<pair<int,int>> adj[N];
vector<int> st,path;
bool onpath[N];
void dfs(int x,int p,int h){
    for (auto u:adj[x]){
        if (u.F==p) continue;
        dis[h][u.F]=dis[h][x]+u.S;
        dfs(u.F,x,h);
    }return;
}
void getpath(int x,int p,int y){
    st.pb(x);
    if (x==y) path=st;
    for (auto u:adj[x]){
        if (u.F==p) continue;
        getpath(u.F,x,y);
    }st.ppb();
    return;
}
int32_t max_score(int32_t nn, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
    n=nn;
    k=K;
    for (int i=0;i<n;i++) adj[i].clear(),onpath[i]=0;
    for (int i=0;i<U.size();i++){
        adj[U[i]].pb({V[i],W[i]});
        adj[V[i]].pb({U[i],W[i]});
    }dis[0][X]=0;
    dfs(X,0,0);
    dis[1][Y]=0;
    dfs(Y,0,1);
    getpath(X,0,Y);
    for (auto u:path) onpath[u]=1;
    priority_queue<vector<int>> pq;
    for (auto u:adj[X]){
        if (!onpath[u.F]) pq.push({-dis[0][u.F],u.F,0});
    }
    for (auto u:adj[Y]){
        if (!onpath[u.F]) pq.push({-dis[1][u.F],u.F,1});
    }
    vector<int> v;v.pb(0);
    while (!pq.empty()){
        int x=pq.top()[1];bool h=pq.top()[2];
        pq.pop();
        v.pb(v.back()+dis[h][x]);
        for (auto u:adj[x]){
            if (dis[h][u.F]<dis[h][x]) continue;
            pq.push({-dis[h][u.F],u.F,h});
        }
    }
    vector<int> p,s,mx;p.resize(path.size());s.resize(path.size());mx.resize(path.size());
    s[s.size()-1]=dis[1][path.back()];
    for (int i=s.size()-2;i>=0;i--) s[i]=s[i+1]+dis[1][path[i]];
    p[0]=dis[0][path[0]];
    for (int i=1;i<p.size();i++) p[i]=p[i-1]+dis[0][path[i]];
    mx[0]=max(dis[0][path[0]],dis[1][path[0]]);
    for (int i=1;i<mx.size();i++) mx[i]=mx[i-1]+max(dis[0][path[i]],dis[1][path[i]]);
    int ans=0;
    for (int i=0;i<path.size();i++){
        for (int j=path.size()-1;j>=0;j--){
            int x=0;
            if (i<j) x=p[i]+s[j];
            else{
                x=mx[i];
                if (j) x-=mx[j-1],x+=p[j-1];
                if (i+1<path.size()) x+=s[i+1];
            }
            int l=0,r=v.size()-1,mid,ansx=0;
            while (l<=r){
                mid=(l+r)/2;
                if (v[mid]+x<=k){
                    ansx=mid+i+1+path.size()-j;
                    l=mid+1;
                }else r=mid-1;
            }ans=max(ans,ansx);
        }
    }
    k-=mx.back();
    if (k<=0) return ans;
    for (int i=0;i<v.size();i++){
        int x=k-v[i];
        if (x<0) break;
        ans=max(ans,(int)2*(int)path.size()+i+min((k-v[i])/6,i));
    }
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0;i<U.size();i++){
      |                  ~^~~~~~~~~
closing.cpp:66:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=1;i<p.size();i++) p[i]=p[i-1]+dis[0][path[i]];
      |                  ~^~~~~~~~~
closing.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i=1;i<mx.size();i++) mx[i]=mx[i-1]+max(dis[0][path[i]],dis[1][path[i]]);
      |                  ~^~~~~~~~~~
closing.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=0;i<path.size();i++){
      |                  ~^~~~~~~~~~~~
closing.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 if (i+1<path.size()) x+=s[i+1];
      |                     ~~~^~~~~~~~~~~~
closing.cpp:91:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~

• 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