oj.uz

Submission #236660

# Submission time Handle Problem Language Result Execution time Memory
236660 2020-06-02T18:48:29 Z andreiomd Transport (COCI19_transport) C++11
26 / 130
 153 ms 9336 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2816 KB Output is correct
2 Correct 25 ms 2944 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3064 KB Output is correct
2 Correct 10 ms 3072 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 6392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 7672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 9336 KB Output isn't correct
2 Halted 0 ms 0 KB -