oj.uz

Submission #834112

# Submission time Handle Problem Language Result Execution time Memory
834112 2023-08-22T10:53:58 Z Liudas Aesthetic (NOI20_aesthetic) C++17
13 / 100
 2000 ms 39316 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
signed main(){
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> tree(N);
    vector<int> vals(M);
    for(int i = 0; i < M; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        tree[a].push_back({b,i});
        tree[b].push_back({a,i});
        vals[i] = c;
    }
    int an = 0;
    for(int i = 0; i < M-1; i ++){
        int tval = *max_element(vals.begin()+i+1, vals.end());
        vals[i] += tval;
        priority_queue<vector<int>> que;
        que.push({0,0});
        int ans = 0;
        vector<bool> vis(N);
        while(!que.empty()){
            int a = -que.top()[0], b = que.top()[1];
            que.pop();
            if(b == N-1){ans = a; break;}
            if(vis[b])continue;
            vis[b] = true;
            for(auto [l, r] : tree[b]){
                que.push({-a-vals[r], l});
            }
        }
        an = max(an, ans);
        vals[i] -= tval;
    }
    cout << an << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1010 ms 592 KB Output is correct
10 Correct 953 ms 532 KB Output is correct
11 Correct 909 ms 472 KB Output is correct
12 Correct 827 ms 480 KB Output is correct
13 Correct 881 ms 500 KB Output is correct
14 Correct 909 ms 496 KB Output is correct
15 Correct 950 ms 468 KB Output is correct
16 Correct 887 ms 468 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1010 ms 592 KB Output is correct
10 Correct 953 ms 532 KB Output is correct
11 Correct 909 ms 472 KB Output is correct
12 Correct 827 ms 480 KB Output is correct
13 Correct 881 ms 500 KB Output is correct
14 Correct 909 ms 496 KB Output is correct
15 Correct 950 ms 468 KB Output is correct
16 Correct 887 ms 468 KB Output is correct
17 Execution timed out 2063 ms 32084 KB Time limit exceeded
18 Halted 0 ms 0 KB -