Submission #787626

#	Time	Username	Problem	Language	Result	Execution time	Memory
787626		aymanrs	Cyberland (APIO23_cyberland)	C++17	21 / 100	937 ms	2097152 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
struct node {
    vector<pair<node*, int>> l;
    long long f = -1;
    bool g = false;
};
void gfs(node* n, node* p){
    for(auto [c, co] : n->l){
        if(c!=p){gfs(c, n);
        n->g |= c->g;}
    }
}
void dfs(node* n, node* p){
    for(auto [c, co] : n->l){
        if(c != p){
            c->f = n->f + co;
            dfs(c, n);
        }
    }
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    node g[N];
    g[0].g =true;
    for(int i = 0;i < M;i++){
        g[x[i]].l.emplace_back(&g[y[i]], c[i]);
        g[y[i]].l.emplace_back(&g[x[i]], c[i]);
    }
    g[H].f = 0;
    gfs(&g[H], NULL);
    for(auto [c, co] : g[H].l){
        if(c->g) {
            c->f = co;
            dfs(c, &g[H]);
        }
    }
    long long ans = g[0].f;
    for(int i = 0;i < N;i++){
        if(!arr[i] && g[i].f != -1) ans = min(ans, g[i].f);
    }
    return ans;
}
// int main(){
//     cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// }

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3