Submission #1214473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214473		spetr	Petrol stations (CEOI24_stations)	C++20	18 / 100	603 ms	13184 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define vlll vector<vector<vector<long long>>>


ll pow(ll x, ll n, ll mod){
    if (n == 0){
        return 1;
    }
ll half = pow(x, n / 2, mod);
ll half_square = (half * half) % mod;

if (n % 2 == 0) {
    return half_square;
} else {
    return (half_square * x) % mod;
}
}   


ll inversion_x(ll x, ll m){
    ll vysledek = pow(x,m-2);
    return vysledek;
}


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

    ll n,k;

    cin >> n >> k;
    vector<vector<vector<ll>>> graf;

    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].push_back({b,c}); graf[b].push_back({a,c});}


    vl pocty;
    for (ll i = 0; i < n; i++){pocty.push_back(0);}

    if (n <= 1000){
    for (ll i = 0; i < n; i++){
        set<ll> visited;
        set<ll> solved;
        vll zasobnik;
        zasobnik.push_back({i, k});
        vl sons;
        for (ll i = 0; i < n; i++){sons.push_back(1);}

        while (zasobnik.size()>0){
            vl prvek = zasobnik[zasobnik.size()-1];
            zasobnik.pop_back();
            ll pos, kapacita;
            pos = prvek[0];
            kapacita = prvek[1];

            auto f = visited.find(pos);
            if (f == visited.end()){
                visited.insert(pos);
                zasobnik.push_back({pos,kapacita});
                for (ll j = 0; j < graf[pos].size(); j++){
                    auto exist = visited.find(graf[pos][j][0]);
                    if (exist == visited.end()){
                        if (kapacita < graf[pos][j][1]){
                            zasobnik.push_back({graf[pos][j][0], k-graf[pos][j][1]});
                        }
                        else{
                            zasobnik.push_back({graf[pos][j][0], kapacita - graf[pos][j][1]});
                        }
                    }
                }
            }

            else{
                solved.insert(pos);
                for (ll j = 0; j < graf[pos].size(); j++){
                    auto exist = solved.find(graf[pos][j][0]);
                    if (exist != solved.end()){
                        if (kapacita < graf[pos][j][1]){
                            pocty[pos] += sons[graf[pos][j][0]];
                        }
                        sons[pos] += sons[graf[pos][j][0]];
                        
                    }
                }

            }

        }
    }

    for (ll i = 0; i < n; i++){
        cout << pocty[i]<< "\n";
    }}

    else{
        for (ll i = 0; i < n; i++){
            ll vzorec = i * ((n-i-1)/k) + (n-i-1)* (i/k);
            cout << vzorec;
        }
    }


}

• Subtask 0: 0 / 0
• Subtask 1: 18 / 18
• Subtask 2: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35