oj.uz

Submission #849918

# Submission time Handle Problem Language Result Execution time Memory
849918 2023-09-15T14:42:33 Z eltu0815 Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 32036 KB 
#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 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 32036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Incorrect 3 ms 15708 KB 1st lines differ - on the 1st token, expected: '30', found: '40'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Incorrect 3 ms 15708 KB 1st lines differ - on the 1st token, expected: '30', found: '40'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Incorrect 3 ms 15708 KB 1st lines differ - on the 1st token, expected: '30', found: '40'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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