oj.uz

Submission #848640

# Submission time Handle Problem Language Result Execution time Memory
848640 2023-09-13T07:19:12 Z eltu0815 Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 25940 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 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);
    
    int ans = 0;
    for(int i = 0; i <= X; ++i) for(int j = X; j < N; ++j) {
        for(int p = 0; p <= Y; ++p) for(int q = Y; q < N; ++q) {
            for(int k = 0; k < N; ++k) c[k] = 0;
            for(int k = i; k <= j; ++k) c[k] = max(c[k], dist1[k]);
            for(int k = p; k <= q; ++k) c[k] = max(c[k], dist2[k]);
            
            ll sum = 0;
            for(int k = 0; k < N; ++k) sum += c[k];
            if(sum <= K) ans = max(ans, j - i + q - p + 2);
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9652 KB Output is correct
5 Correct 2 ms 9656 KB Output is correct
6 Correct 32 ms 9636 KB Output is correct
7 Correct 25 ms 9656 KB Output is correct
8 Correct 10 ms 9564 KB Output is correct
9 Correct 3 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9652 KB Output is correct
5 Correct 2 ms 9656 KB Output is correct
6 Correct 32 ms 9636 KB Output is correct
7 Correct 25 ms 9656 KB Output is correct
8 Correct 10 ms 9564 KB Output is correct
9 Correct 3 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 105 ms 9640 KB Output is correct
13 Correct 66 ms 9640 KB Output is correct
14 Correct 194 ms 9640 KB Output is correct
15 Correct 86 ms 9636 KB Output is correct
16 Correct 3 ms 9564 KB Output is correct
17 Correct 4 ms 9656 KB Output is correct
18 Correct 10 ms 9564 KB Output is correct
19 Execution timed out 1041 ms 9564 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9652 KB Output is correct
5 Correct 2 ms 9656 KB Output is correct
6 Correct 32 ms 9636 KB Output is correct
7 Correct 25 ms 9656 KB Output is correct
8 Correct 10 ms 9564 KB Output is correct
9 Correct 3 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 105 ms 9640 KB Output is correct
13 Correct 66 ms 9640 KB Output is correct
14 Correct 194 ms 9640 KB Output is correct
15 Correct 86 ms 9636 KB Output is correct
16 Correct 3 ms 9564 KB Output is correct
17 Correct 4 ms 9656 KB Output is correct
18 Correct 10 ms 9564 KB Output is correct
19 Execution timed out 1041 ms 9564 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9560 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 3 ms 9560 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 3 ms 9560 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 3 ms 9560 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 3 ms 9560 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -