oj.uz

Submission #1070799

# Submission time Handle Problem Language Result Execution time Memory
1070799 2024-08-22T18:40:17 Z MohamedFaresNebili Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 34768 KB 
    #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 = X; l >= 0; l--) {
                    for(int i = X; i < N; i++) {
                        for(int j = Y; j >= 0; j--) {
                            for(int e = Y; e < N; e++) {
                                int lo = max(l, j), hi = min(i, e);
                                long long calc = 0;
                                if(lo > hi) {
                                    calc += sum(l, i, pL);
                                    calc += sum(j, e, pR);
                                }
                                else {
                                    calc += sum(l, i, pL);
                                    calc += sum(j, e, pR);
                                    calc -= sum(lo, hi, pM);
                                }
                                if(calc <= K) res = max(res,  i - l + e - j + 2);
                            }
                        }
                    }
                }
                return res;
            }

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5980 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 1068 ms 34768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 22 ms 5980 KB Output is correct
7 Correct 17 ms 5980 KB Output is correct
8 Correct 7 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 1 ms 5980 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 22 ms 5980 KB Output is correct
7 Correct 17 ms 5980 KB Output is correct
8 Correct 7 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 1 ms 5980 KB Output is correct
12 Correct 65 ms 5980 KB Output is correct
13 Correct 33 ms 5976 KB Output is correct
14 Correct 124 ms 6020 KB Output is correct
15 Correct 45 ms 6232 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 9 ms 6044 KB Output is correct
19 Execution timed out 1044 ms 5980 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 22 ms 5980 KB Output is correct
7 Correct 17 ms 5980 KB Output is correct
8 Correct 7 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 1 ms 5980 KB Output is correct
12 Correct 65 ms 5980 KB Output is correct
13 Correct 33 ms 5976 KB Output is correct
14 Correct 124 ms 6020 KB Output is correct
15 Correct 45 ms 6232 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 9 ms 6044 KB Output is correct
19 Execution timed out 1044 ms 5980 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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