Submission #1212427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212427		Aviansh	Closing Time (IOI23_closing)	C++20	75 / 100	1026 ms	2162688 KiB

closing

#include "closing.h"

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

using namespace std;

void dfs(int st, vector<array<int,2>>g[], int p, long long dist[], long long d){
    dist[st]=d;
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,st,dist,d+e[1]);
    }
}
vector<int>xypath;
void dfsxy(int st, vector<array<int,2>>g[], int p, vector<int>&path, int y){
    path.push_back(st);
    if(st==y){
        xypath.clear();
        for(int i : path){
            xypath.push_back(i);
        }
    }
    for(array<int,2>e : g[st]){
        if(e[0]==p)
            continue;
        dfsxy(e[0],g,st,path,y);
    }
    path.pop_back();
}

int max_score(int n, int x, int y, long long k, vector<int> u, vector<int> v, vector<int> w) {
    vector<array<int,2>>g[n];
    int m = u.size();
    for(int i = 0;i<m;i++){
        g[u[i]].push_back({v[i],w[i]});
        g[v[i]].push_back({u[i],w[i]});
    }
    long long distx[n], disty[n];
    dfs(x,g,-1,distx,0);
    dfs(y,g,-1,disty,0);
    long long cost1[n],cost2[n];
    for(int i = 0;i<n;i++){
        cost1[i]=min(distx[i],disty[i]);
        cost2[i]=max(distx[i],disty[i])-cost1[i];
    }
    vector<int>pt;
    dfsxy(x,g,-1,pt,y);
    //case 1:
    int ans1 = 0;
    //only till level 1.
    priority_queue<long long,vector<long long>,greater<long long>>pq;
    for(int i = 0;i<n;i++){
        pq.push(cost1[i]);
    }
    long long curk = 0;
    while(curk<=k&&pq.size()){
        long long a = pq.top();
        pq.pop();
        if(curk+a>k)
            break;
        ans1++;
        curk+=a;
    }
    //case 2:
    bool man[n];
    fill(man,man+n,0);
    for(int i : xypath){
        man[i]=1;
    }
    long long dp[n][2*n+1];
    // Initialize all states to a large value (invalid)
    for (int i = 0; i < n; i++) {
        fill(dp[i], dp[i] + 2*n + 1, (long long)2e18);
    }

    // Base case for the first bag (i=0)
    if (man[0]) {
        // Mandatory: must take at least one item
        dp[0][1] = cost1[0];
        dp[0][2] = cost1[0] + cost2[0]; // Fixed: use cost2[0]
    } else {
        // Non-mandatory: can skip, take one, or take two
        dp[0][0] = 0;
        dp[0][1] = cost1[0];
        dp[0][2] = cost1[0] + cost2[0]; // Fixed: use cost2[0]
    }

    // Fill DP table for bags 1 to n-1
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= 2*n; j++) { // Include j=0
            if (man[i]) {
                // Mandatory bag: must take at least one item
                if (j >= 1) {
                    // Take one item
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost1[i]);
                }
                if (j >= 2) {
                    // Take two items
                    dp[i][j] = min(dp[i][j], dp[i-1][j-2] + cost1[i] + cost2[i]);
                }
            } else {
                // Non-mandatory bag: skip, take one, or take two
                dp[i][j] = min(dp[i][j], dp[i-1][j]); // Skip
                if (j >= 1) {
                    // Take one item
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost1[i]);
                }
                if (j >= 2) {
                    // Take two items
                    dp[i][j] = min(dp[i][j], dp[i-1][j-2] + cost1[i] + cost2[i]);
                }
            }
            // Cap the value to avoid overflow
            if (dp[i][j] > (long long)2e18) {
                dp[i][j] = (long long)2e18;
            }
        }
    }

    // Find the maximum items from the last row (all bags processed)
    int ans2 = 0;
    for (int j = 0; j <= 2*n; j++) {
        if (dp[n-1][j] <= k) {
            ans2 = max(ans2, j);
        }
    }
    return max(ans1,ans2);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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