Submission #1070841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070841		MohamedFaresNebili	Closing Time (IOI23_closing)	C++17	21 / 100	1098 ms	38268 KiB

closing

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

                    using namespace std;

                    vector<pair<int, long long>> adj[200005];
                    long long D[200005][2];
                    vector<long long> pL, pR, pM;
                    void dfs(int X, int p, int st) {
                        for(auto u : adj[X]) {
                            if(u.first == p) continue;
                            D[u.first][st] = D[X][st] + u.second;
                            dfs(u.first, X, st);
                        }
                    }
                    long long sum(int l, int r, vector<long long> arr) {
                        return arr[r] - (l > 0 ? arr[l - 1] : 0);
                    }

                    int max_score(int N, int X, int Y, long long K,
                        vector<int> U, vector<int> V, vector<int> W) {
                        pL.resize(N); pR.resize(N); pM.resize(N);
                        for(int l = 0; l < N; l++) D[l][0] = D[l][1] = 2e18 + 7, adj[l].clear();
                        for(int l = 0; l < N - 1; l++) {
                            adj[U[l]].push_back({V[l], W[l]});
                            adj[V[l]].push_back({U[l], W[l]});
                        }
                        if(X > Y) swap(X, Y);
                        D[X][0] = 0, D[Y][1] = 0;
                        dfs(X, X, 0); dfs(Y, Y, 1);
                        for(int l = 0; l < N; l++) {
                            pL[l] = D[l][0];
                            pR[l] = D[l][1];
                            pM[l] = min(D[l][0], D[l][1]);
                            if(l > 0) {
                                pL[l] += pL[l - 1];
                                pR[l] += pR[l - 1];
                                pM[l] += pM[l - 1];
                            }
                        }
                        int res = 0;
                        for(int l = 0; l < N; l++) {
                            for(int i = l; i < N; i++) {
                                int lo = l, hi = i;
                                long long calc = sum(l, i, pL) + sum(l, i, pR) - sum(l, i, pM);
                                if(calc > K) continue;
                                int cur = 2 * (i - l + 1);
                                while(lo > 0 || hi < N - 1) {
                                    if(lo == 0) {
                                        ++hi; calc += min(D[hi][0], D[hi][1]);
                                        if(calc > K) {
                                            hi--; break;
                                        }
                                      	cur++;
                                    }
                                    else if(hi == N - 1) {
                                        --lo; calc += min(D[lo][0], D[lo][1]);
                                        if(calc > K) {
                                            lo++; break;
                                        } cur++;
                                    }
                                    else {
                                        int a = lo - 1, b = hi + 1;
                                        long long x = min(D[a][0], D[a][1]);
                                        long long y = min(D[b][0], D[b][1]);
                                      	if(calc + min(x, y) > K) break;
                                      	cur++;
                                        if(x <= y) {
                                            calc += x; lo--;
                                        }
                                        else { calc += y; hi++; }
                                    }
                                }
                                if(X >= lo && Y <= hi) res = max(res, cur);
                            }
                        }

                        vector<int> belong(N, -1);
                        priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;
                        pq.push({0, X, 0}); pq.push({0, Y, 1});
                        int cur = 0; long long calc = 0;
                        while(!pq.empty()) {
                            int a = pq.top()[1], st = pq.top()[2];
                            long long w = pq.top()[0]; pq.pop();
                            if(calc + w > K) break;
                            if(belong[a] != -1) continue;
                            belong[a] = st; calc += w; cur++;
                            if(a > 0) {
                                int b = a - 1;
                                if(belong[b] == -1) {
                                    array<long long, 3> arr = {D[b][st], b, st};
                                    pq.push(arr);
                                }
                            }
                            if(a < N - 1) {
                                int b = a + 1;
                                if(belong[b] == -1) {
                                    array<long long, 3> arr = {D[b][st], b, st};
                                    pq.push(arr);
                                }
                            }
                        }
                        res = max(res, cur);
                        return res;
                    }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 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