oj.uz

Submission #834329

# Submission time Handle Problem Language Result Execution time Memory
834329 2023-08-22T13:04:52 Z Liudas Aesthetic (NOI20_aesthetic) C++17
20 / 100
 2000 ms 34508 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
vector<int> path, fpath;
void DFS(int head, int par, vector<vector<pair<int, int>>> &tree){
    if(head == tree.size()-1){
        fpath = path;
        return;
    }
    for(auto[l, r] : tree[head]){
        if(l != par){
            path.push_back(r);
            DFS(l, head, tree);
            path.pop_back();
        }
    }
}
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;
    }
    if(M == N - 1){
        vector<int> maxsuff(N);
        for(int i = N-2; i >= 0; i --){
            maxsuff[i] = max(vals[i+1], maxsuff[i+1]);
        }
        DFS(0, -1, tree);
        int ans = 0;
        for(int i : fpath){
            ans = max(ans, maxsuff[i]);
        }
        for(int i : fpath){
            ans += vals[i];
        }
        cout << ans << endl;
    }
    else if(*max_element(vals.begin(), vals.end()) == 1){
        vector<int> reach(N, 0);
        vector<int> md(N, -1);
        queue<vector<int>> que;
        que.push({0, 0});
        while(!que.empty()){
            int a = que.front()[0], b = que.front()[1];
            que.pop();
            if(md[b] == -1){
                md[b] = a;
                for(auto[l, r] : tree[b]){
                    que.push({a+1, l});
                }
            }
            if(md[b] == a){
                reach[b]++;
            }
        }
        vector<int> dist(md.back()+1);
        for(int i = 0; i < N; i ++){
            dist[md[i]] += reach[i];
        }
        bool add = true;
        dist[0] = 2;
        dist.back() = 2;
        for(int i :dist){
            if(i < 2)add = false;
        }
        if(add){
            cout << md.back() << endl;
        }
        else{
            cout << md.back() + 1 << endl;
        }
    }
    else{
        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;
}

Compilation message

Aesthetic.cpp: In function 'void DFS(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
Aesthetic.cpp:10:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(head == tree.size()-1){
      |        ~~~~~^~~~~~~~~~~~~~~~

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 2 ms 340 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 260 KB Output is correct
7 Correct 2 ms 212 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 2 ms 340 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 260 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1022 ms 540 KB Output is correct
10 Correct 947 ms 532 KB Output is correct
11 Correct 831 ms 472 KB Output is correct
12 Correct 818 ms 476 KB Output is correct
13 Correct 876 ms 468 KB Output is correct
14 Correct 890 ms 496 KB Output is correct
15 Correct 912 ms 512 KB Output is correct
16 Correct 884 ms 500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 28108 KB Output is correct
2 Correct 359 ms 28380 KB Output is correct
3 Correct 374 ms 27960 KB Output is correct
4 Correct 333 ms 27848 KB Output is correct
5 Correct 323 ms 28056 KB Output is correct
6 Correct 402 ms 28808 KB Output is correct
7 Correct 351 ms 28520 KB Output is correct
8 Correct 353 ms 28620 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 34508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 34508 KB Output isn't correct
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 2 ms 340 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 260 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1022 ms 540 KB Output is correct
10 Correct 947 ms 532 KB Output is correct
11 Correct 831 ms 472 KB Output is correct
12 Correct 818 ms 476 KB Output is correct
13 Correct 876 ms 468 KB Output is correct
14 Correct 890 ms 496 KB Output is correct
15 Correct 912 ms 512 KB Output is correct
16 Correct 884 ms 500 KB Output is correct
17 Correct 365 ms 28108 KB Output is correct
18 Correct 359 ms 28380 KB Output is correct
19 Correct 374 ms 27960 KB Output is correct
20 Correct 333 ms 27848 KB Output is correct
21 Correct 323 ms 28056 KB Output is correct
22 Correct 402 ms 28808 KB Output is correct
23 Correct 351 ms 28520 KB Output is correct
24 Correct 353 ms 28620 KB Output is correct
25 Execution timed out 2044 ms 26144 KB Time limit exceeded
26 Halted 0 ms 0 KB -