Submission #1207339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207339		spetr	Harbingers (CEOI09_harbingers)	C++20	20 / 100	1096 ms	35568 KiB

harbingers

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

#define ll long long
#define vl vector<long long>
#define vll vector<vector<long long>>



int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);

    ll n;
    cin >> n;

    vll graf;
    map<vl,ll> ceny;
    vll posta {{0,0,0,0}};
    for (ll i = 0; i < n; i++){
        graf.push_back({});
    }

    for (ll i = 0; i < n-1; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        graf[a-1].push_back(b-1);
        graf[b-1].push_back(a-1);
        ceny[{a-1,b-1}] = c;
        ceny[{b-1,a-1}] = c;

    }

    for (ll i = 0; i < n-1; i++){
        ll a,b;
        cin >> a >> b;
        posta.push_back({a,b,-1,0}); // pointer zpět a skore
    }

    vl zasobnik {0};
    set<ll> mnozina;

    while (zasobnik.size() > 0){
        ll prvek = zasobnik[zasobnik.size()-1];
        zasobnik.pop_back();
        auto visited = mnozina.find(prvek);

        if (visited == mnozina.end()){
            mnozina.insert(prvek);
            for (ll i = 0; i < graf[prvek].size(); i++){
                auto je = mnozina.find(graf[prvek][i]);
                if (je == mnozina.end()){
                    posta[graf[prvek][i]][2] = prvek;
                    zasobnik.push_back(graf[prvek][i]);
                }
            }

            ll pos = prvek;
            ll distance = 0;
            ll optimum = 1000000000;
            while (pos != 0){
                distance += ceny[{pos, posta[pos][2]}];
                pos = posta[pos][2];
                optimum = min(optimum, distance*posta[prvek][1] + posta[prvek][0] + posta[pos][3]);

            }
            optimum = min(optimum,  distance*posta[prvek][1] + posta[prvek][0]);
            posta[prvek][3] = optimum;
        }
    }
    for (ll i = 1; i < n; i++){
        cout << posta[i][3] << " ";
    }

    return 0;
}

• Subtask 1: 20 / 100