oj.uz

답안 #1070799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070799 2024-08-22T18:40:17 Z MohamedFaresNebili 봉쇄 시간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -