Submission #849918

#	Time	Username	Problem	Language	Result	Execution time	Memory
849918		eltu0815	Closing Time (IOI23_closing)	C++17	0 / 100	1069 ms	32036 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
#define MAX 200005
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int visited[MAX];
vector<pii> graph[MAX];
ll dist1[MAX], dist2[MAX];

void dfs1(int node) {
    visited[node] = 1;
    for(auto [v, w] : graph[node]) {
        if(visited[v]) continue;
        dist1[v] = dist1[node] + w;
        dfs1(v);
    }
}

void dfs2(int node) {
    visited[node] = 1;
    for(auto [v, w] : graph[node]) {
        if(visited[v]) continue;
        dist2[v] = dist2[node] + w;
        dfs2(v);
    }
}

ll L[MAX], R[MAX];
ll mid[MAX];
ll ans[MAX];
ll c[MAX];

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    for(int i = 0; i < N; ++i) graph[i].clear();
    for(int i = 0; i < N - 1; ++i) {
        graph[U[i]].push_back({V[i], W[i]});
        graph[V[i]].push_back({U[i], W[i]});
    }
    
    for(int i = 0; i < N; ++i) visited[i] = dist1[i] = 0;
    dfs1(X);
    
    for(int i = 0; i < N; ++i) visited[i] = dist2[i] = 0;
    dfs2(Y);
    
    for(int i = 0; i < N; ++i) c[i] = 0;
    
    int p = X, q = Y, id = 1;
    for(int i = 1; i <= 2 * N; ++i) mid[i] = (ll)(1e18);
    while(true) {
        if(q == X - 1 && p == Y + 1) break;
        else if(q == X - 1) mid[id] = mid[id - 1] + dist1[p] - c[p], c[p] = dist1[p], ++p;
        else if(p == Y + 1) mid[id] = mid[id - 1] + dist2[q] - c[q], c[q] = dist2[q], --q;
        else if(dist1[p] - c[p] <= dist2[q] - c[q]) mid[id] = mid[id - 1] + dist1[p] - c[p], c[p] = dist1[p], ++p;
        else mid[id] = mid[id - 1] + dist2[q] - c[q], c[q] = dist2[q], --q;
        ++id;
    }
    
    p = X, q = X, id = 1;
    for(int i = 1; i <= 2 * N; ++i) L[i] = (ll)(1e18);
    while(true) {
        if(p == 0 && q == 0) break;
        else if(p == q) --p, L[id] = L[id - 1] + dist1[p];
        else if(p == 0) --q, L[id] = L[id - 1] + dist2[q] - dist1[q];
        else {
            if(dist2[q - 1] - dist1[q - 1] <= dist1[p - 1]) --q, L[id] = L[id - 1] + dist2[q] - dist1[q];
            else --p, L[id] = L[id - 1] + dist1[p];
        }
        ++id;
    }
    
    p = Y, q = Y, id = 1;
    for(int i = 1; i <= 2 * N; ++i) R[i] = (ll)(1e18);
    while(true) {
        if(p == N - 1 && q == N - 1) break;
        else if(p == q) ++p, R[id] = R[id - 1] + dist2[p];
        else if(p == N - 1) ++q, R[id] = R[id - 1] + dist1[q] - dist2[q];
        else {
            if(dist1[q + 1] - dist2[q + 1] <= dist2[p + 1]) ++q, R[id] = R[id - 1] + dist1[q] - dist2[q];
            else ++p, R[id] = R[id - 1] + dist2[p];
        }
        ++id;
    }
    
    for(int i = 0; i <= 2 * N; ++i) ans[i] = mid[i];
    for(int i = 0; i <= 2 * N; ++i) for(int j = 0; j <= i; ++j) ans[i] = min(ans[i], ans[j] + L[i - j]);
    for(int i = 0; i <= 2 * N; ++i) for(int j = 0; j <= i; ++j) ans[i] = min(ans[i], ans[j] + R[i - j]);
    
    int mx = 0;
    for(int i = 0; i <= 2 * N; ++i) if(ans[i] <= K) mx = i;
    return mx;
}

/*
3
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3

4 0 3 20
0 1 18
1 2 1
2 3 19

4 0 1 20
0 1 18
1 2 1
2 3 19
*/

• 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