oj.uz

Submission #1070785

# Submission time Handle Problem Language Result Execution time Memory
1070785 2024-08-22T18:29:07 Z MohamedFaresNebili Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 28620 KB 
#include <bits/stdc++.h>
#include "closing.h"

        using namespace std;

        vector<pair<int, long long>> adj[200005];
        long long D[200005][2];
        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);
            }
        }

        int max_score(int N, int X, int Y, long long K,
            vector<int> U, vector<int> V, vector<int> W) {
            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);
            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) {
                                for(int f = l; f <= i; f++)
                                    calc += D[f][0];
                                for(int f = j; f <= e; f++)
                                    calc += D[f][1];
                            }
                            else {
                                for(int f = l; f <= i; f++)
                                    calc += D[f][0];
                                for(int f = j; f <= e; f++)
                                    calc += D[f][1];
                                for(int f = lo; f <= hi; f++)
                                    calc -= min(D[f][0], D[f][1]);
                            }
                            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 1 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 1043 ms 28620 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 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 18 ms 5980 KB Output is correct
7 Correct 14 ms 5804 KB Output is correct
8 Correct 5 ms 6036 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 18 ms 5980 KB Output is correct
7 Correct 14 ms 5804 KB Output is correct
8 Correct 5 ms 6036 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 63 ms 5980 KB Output is correct
13 Correct 40 ms 5976 KB Output is correct
14 Correct 110 ms 5980 KB Output is correct
15 Correct 63 ms 6032 KB Output is correct
16 Correct 3 ms 5976 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Execution timed out 1098 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 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 18 ms 5980 KB Output is correct
7 Correct 14 ms 5804 KB Output is correct
8 Correct 5 ms 6036 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 63 ms 5980 KB Output is correct
13 Correct 40 ms 5976 KB Output is correct
14 Correct 110 ms 5980 KB Output is correct
15 Correct 63 ms 6032 KB Output is correct
16 Correct 3 ms 5976 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 5 ms 5980 KB Output is correct
19 Execution timed out 1098 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 1 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 1 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 1 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 1 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 1 ms 5980 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -