Submission #1074382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074382		anango	Closing Time (IOI23_closing)	C++17	83 / 100	1067 ms	45128 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
#include <vector>

#define int long long
using namespace std;
int n;
int INF = 1LL<<61;
vector<int> dist1;
vector<int> dist2;
vector<vector<pair<int,int>>> adjlist;

void dfs1(int node, int par) {
    for (pair<int,int> j:adjlist[node]) {
        if (j.first!=par) {
            dist1[j.first] = dist1[node]+j.second;
            dfs1(j.first,node);
        }
    }
}


void dfs2(int node, int par) {
    for (pair<int,int> j:adjlist[node]) {
        if (j.first!=par) {
            dist2[j.first] = dist2[node]+j.second;
            dfs2(j.first,node);
        }
    }
}


signed max_score(signed N, signed X, signed Y, long long K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W)  {
    n=N;
    dist1=dist2=vector<int>(n,INF);
    adjlist=vector<vector<pair<int,int>>>(n);
    for (int i=0; i<n-1; i++) {
        adjlist[U[i]].push_back({V[i],W[i]});
        adjlist[V[i]].push_back({U[i],W[i]});
    }
    dist1[X] = 0; dist2[Y] = 0;
    dfs1(X,-1); dfs2(Y,-1);
    vector<int> dp(2*n+1,INF); //max cost to get this amount of score
    dp[0] = 0;

    vector<int> sc1cost(dist1.begin(), dist1.end()); 
    vector<int> sc2cost(dist2.begin(), dist2.end());
    for (int i=0; i<n; i++) {
        if (dist1[i]>dist2[i]) {
            swap(sc1cost[i],sc2cost[i]);
        }
    }
    for (int i=0; i<n; i++) {
        //cout << i <<" " << dist1[i] <<" " << dist2[i] << endl;
    }

    int mans = -1;

    //first case: we do not fill up the path from X to Y
    //in that case we don't want to place 2s anywhere
    //so just take the cheapest 1s
    int ct=0;
    vector<int> indices(n); iota(indices.begin(), indices.end(), (int)0);
    sort(indices.begin(), indices.end(), [&](const int i1, const int i2) {
        return sc1cost[i1]<sc1cost[i2];
    });
    int parsum = 0;
    for (int i=0; i<n; i++) {
        if (parsum+sc1cost[indices[i]]>K) break;
        parsum+=sc1cost[indices[i]];
        ct++;
    }
    mans=max(mans,ct);
    if (dist1[Y]>2*K) {
        return mans;
    }
    //second case: need to take everything on the path from X to Y at least 1
    //so we consider the 1s and 2s separately 
    int usedcost = 0;
    vector<int> pathvals;
    vector<pair<int,int>> remcosts;
    int got = 0;
    for (int i=0; i<n; i++) {
        if (dist1[i]+dist2[i]==dist1[Y]) {
            pathvals.push_back(i);
            usedcost+=sc1cost[i];
            got++;
            remcosts.push_back({sc2cost[i]-sc1cost[i],INF});
        }
        else {
            remcosts.push_back({sc1cost[i],sc2cost[i]});
        }
    }
    
    K-=usedcost;

    for (int i=0; i<remcosts.size(); i++) {
        for (int prevscore=2*n; prevscore>=0; prevscore--) {
            if (prevscore<=2*n-1) {
                dp[prevscore+1] = min(dp[prevscore+1],dp[prevscore]+remcosts[i].first);
            }
            if (prevscore<=2*n-2) {
                dp[prevscore+2] = min(dp[prevscore+2],dp[prevscore]+remcosts[i].second);
            }
        }
    }

    for (int i=0; i<=2*n; i++) {
        //cout << i <<" " << dp[i] << endl;
        if (dp[i]<=K) {
            mans=max(mans,i+got);
        }
    }
    return mans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:97:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=0; i<remcosts.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~

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