Submission #236660

#	Time	Username	Problem	Language	Result	Execution time	Memory
236660		andreiomd	Transport (COCI19_transport)	C++11	26 / 130	153 ms	9336 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

typedef pair < int, int > PII;
typedef pair < PII, ll > Type;

const int NMAX = 1e5 + 5;

int N, A[NMAX];

vector < PII > G[NMAX];

long long ans = 0;

queue < Type > Q;

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for(int i = 1; i <= N; ++i)
        cin >> A[i];

    for(int i = 1; i < N; ++i)
    {
        int X = 0, Y = 0, C = 0;
        cin >> X >> Y >> C;

        G[X].push_back({C, Y});
        G[Y].push_back({C, X});
    }

    return;
}

static inline void Brute_Force ()
{
    for(int i = 1; i <= N; ++i)
    {
        Q.push({{i, 0}, A[i]});

        while(!Q.empty())
        {
            int Node = Q.front().first.first, from = Q.front().first.second;
            long long x = Q.front().second;

            Q.pop();

            for(auto it : G[Node])
                if(it.second != from && x >= it.first)
                {
                    ++ans;

                    Q.push({{it.second, Node}, x - 1LL * it.first + 1LL * A[it.second]});
                }
        }
    }

    cout << ans << '\n';

    return;
}

int main()
{
    Read();

    if(N <= 5e3)
        Brute_Force();

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13