oj.uz

Submission #834327

# Submission time Handle Problem Language Result Execution time Memory
834327 2023-08-22T13:04:06 Z Liudas Aesthetic (NOI20_aesthetic) C++17
7 / 100
 2000 ms 48228 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<pair<int, int>> pairs(N);
    vector<int> vals(M);
    for(int i = 0; i < M; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        pairs[i] = {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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 36988 KB Output is correct
2 Correct 375 ms 37076 KB Output is correct
3 Correct 377 ms 36504 KB Output is correct
4 Correct 436 ms 36588 KB Output is correct
5 Correct 346 ms 36692 KB Output is correct
6 Correct 384 ms 37480 KB Output is correct
7 Correct 343 ms 37324 KB Output is correct
8 Correct 375 ms 37452 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 48228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 48228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -