Submission #1092198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092198		Trisanu_Das	Aesthetic (NOI20_aesthetic)	C++17	20 / 100	2073 ms	39328 KiB

Aesthetic

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> path, fpath;
void DFS(int head, int par, vector<vector<pair<int, int>>> &adj){
    if(head == adj.size() - 1){
        fpath = path;
        return;
    }
    for(auto[l, r] : adj[head]){
        if(l != par){
            path.push_back(r);
            DFS(l, head, adj);
            path.pop_back();
        }
    }
}
signed main(){
    int N, M; cin >> N >> M;
    vector<vector<pair<int, int>>> adj(N);
    vector<int> vals(M);
    for(int i = 0; i < M; i ++){
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        vals[i] = w;
    }
    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, adj);
        int ans = 0;
        for(int i : fpath) ans = max(ans, maxsuff[i]);
        for(int i : fpath) ans += vals[i];
        cout << ans << '\n';
    }
    else{
        int ans = 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>> q;
            q.push({0, 0});
            int curr = 0;
            vector<bool> vis(N, false);
            while(!q.empty()){
                int a = -q.top()[0], b = q.top()[1];
                q.pop();
                if(b == N - 1){curr = a; break;}
                if(vis[b])continue;
                vis[b] = true;
                for(auto [l, r] : adj[b]) q.push({-a - vals[r], l});
            }
            ans = max(ans, curr);
            vals[i] -= tval;
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

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:7: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]
    7 |     if(head == adj.size() - 1){
      |        ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27