Submission #1011572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1011572	2024-06-30T16:13:49 Z	VMaksimoski008	Closing Time (IOI23_closing)	C++17	8 / 100	96 ms	35520 KB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
 
int n, x, y;
long long k;
vector<vector<pair<int, int> >> graph;
const int maxn = 2e5 + 5;
using ll = long long;
ll dist[2][maxn];
 
void dfs(int u, int p, int t) {
    for(auto &[v, w] : graph[u]) {
        if(v == p) continue;
        dist[t][v] = dist[t][u] + w;
        dfs(v, u, t);
    }
}
 
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    x = X;
    y = Y;
    k = K;
    graph.resize(n);
    if(x > y) swap(x, y);
 
    bool line = 1;
    for(int i=0; i<n-1; i++) {
        if(abs(U[i] - V[i]) != 1) line = 0;
        graph[U[i]].push_back({ V[i], W[i] });
        graph[V[i]].push_back({ U[i], W[i] });
    }
 
    if(line && n <= 500) {
        int ans = 0;
        dfs(x, x, 0);
        dfs(y, y, 1);
 
        ll pref[n][2];
        memset(pref, 0, sizeof(pref));
        pref[0][0] = min(dist[0][0], dist[1][0]);
        pref[0][1] = max(dist[0][0], dist[1][0]);
        priority_queue<ll> pq;
        pq.push(-pref[0][0]);
        for(int i=1; i<n; i++) {
            pref[i][0] = pref[i-1][0] + min(dist[1][i], dist[0][i]);
            pref[i][1] = pref[i-1][1] + max(dist[1][i], dist[0][i]);
            pq.push(-min(dist[0][i], dist[1][i]));
        }

        int res = 0;
        ll sum = 0;
        while(!pq.empty()) {
            int u = -pq.top(); pq.pop();
            // cout << u << '\n';
            if(sum + u > k) break;
            sum += u;
            res++;
        }

        auto query = [&](int l, int r, int t) {
            return pref[r][t] - (l ? pref[l-1][t] : 0);
        };

        for(int i=0; i<=x; i++) {
            for(int j=y; j<n; j++) {
                if(query(i, j, 0) > k) break;
                int ans2 = j - i + 1;

                // for(int x=p; p<=j; p++) {
                //     int l=p, r=j, pos=p-1;
                //     while(l <= r) {
                //         int mid = (l + r) / 2;
                //         if(query(p, mid, 1) + query(i, j, 0) <= k) pos = mid, l = mid + 1;
                //         else r = mid - 1;
                //     }
                //     ans = max(ans, j - i + 1 + pos - p + 1);
                // }

                ans = max(ans, ans2);
            }
        }
 
        return max(ans, res);
    }
 
    int ans = 0;
    ll total = k;
    dfs(x, x, 0);
    dfs(y, y, 1);
    
    vector<ll> v;
    for(int i=0; i<2; i++)
        for(int j=0; j<n; j++) v.push_back(dist[i][j]);
    sort(v.begin(), v.end());
 
    for(auto &x : v) {
        if(x > total) break;
        ans++;
        total -= x;
    }
 
    for(int i=0; i<n; i++) {
        graph[i].clear();
        for(int j=0; j<2; j++) dist[j][i] = 0;
    }
 
    return ans;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	29892 KB	Output is correct
2	Correct	96 ms	35520 KB	Output is correct
3	Correct	56 ms	2896 KB	Output is correct

Subtask #2
0.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	344 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #3
0.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	344 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #4
0.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	344 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #5
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Submission #1011572

Compilation message