oj.uz

Submission #826844

# Submission time Handle Problem Language Result Execution time Memory
826844 2023-08-16T05:24:30 Z IBory Traffic (CEOI11_tra) C++17
100 / 100
 835 ms 61580 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 300003;
int X[MAX], Y[MAX], U[MAX], D[MAX];
bool V[MAX];
vector<int> G[MAX], RG[MAX];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M, A, B;
    cin >> N >> M >> A >> B;
    for (int i = 1; i <= N; ++i) cin >> X[i] >> Y[i];
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        G[a].push_back(b);
        RG[b].push_back(a);
        if (c == 2) {
            G[b].push_back(a);
            RG[a].push_back(b);
        }
    }

    vector<pii> L, R;
    for (int i = 1; i <= N; ++i) {
        if (X[i] == 0) L.emplace_back(Y[i], i);
    }
    sort(L.begin(), L.end(), greater<pii>());

    queue<int> Q;
    for (auto [_, n] : L) {
        V[n] = 1;
        Q.push(n);
    }
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (int next : G[cur]) {
            if (V[next]) continue;
            V[next] = 1;
            Q.push(next);
        }
    }
    for (int i = 1; i <= N; ++i) {
        if (X[i] == A && V[i]) R.emplace_back(Y[i], i);
    }
    sort(R.begin(), R.end(), greater<pii>());

    memset(U, 0x3f, sizeof(U));
    priority_queue<pii, vector<pii>, greater<pii>> PQ1;
    for (int i = 0; i < R.size(); ++i) {
        auto [_, n] = R[i];
        PQ1.emplace(U[n] = i, n);
    }
    while (!PQ1.empty()) {
        auto [cd, cur] = PQ1.top(); PQ1.pop();
        for (int next : RG[cur]) {
            if (U[next] <= U[cur]) continue;
            PQ1.emplace(U[next] = U[cur], next);
        }
    }

    memset(D, 0xff, sizeof(D));
    priority_queue<pii> PQ2;
    for (int i = 0; i < R.size(); ++i) {
        auto [_, n] = R[i];
        PQ2.emplace(D[n] = i, n);
    }
    while (!PQ2.empty()) {
        auto [cd, cur] = PQ2.top(); PQ2.pop();
        for (int next : RG[cur]) {
            if (D[next] >= D[cur]) continue;
            PQ2.emplace(D[next] = D[cur], next);
        }
    }

    // for (int i = 1; i <= N; ++i) cout << U[i] << ' ';
    // cout << '\n';
    // for (int i = 1; i <= N; ++i) cout << D[i] << ' ';
    // cout << '\n';

    for (auto [_, n] : L) {
        int ans = max(0, D[n] - U[n] + 1);
        cout << ans << '\n';
    }

    return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < R.size(); ++i) {
      |                     ~~^~~~~~~~~~
tra.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < R.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16728 KB Output is correct
2 Correct 10 ms 16728 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16728 KB Output is correct
5 Correct 8 ms 16700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16788 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 8 ms 16716 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 9 ms 16852 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16868 KB Output is correct
2 Correct 11 ms 17264 KB Output is correct
3 Correct 10 ms 17084 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18132 KB Output is correct
2 Correct 48 ms 21744 KB Output is correct
3 Correct 24 ms 19232 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20444 KB Output is correct
2 Correct 68 ms 23020 KB Output is correct
3 Correct 34 ms 21424 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23908 KB Output is correct
2 Correct 101 ms 26992 KB Output is correct
3 Correct 147 ms 28680 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 26700 KB Output is correct
2 Correct 100 ms 27068 KB Output is correct
3 Correct 126 ms 29308 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 32192 KB Output is correct
2 Correct 203 ms 35008 KB Output is correct
3 Correct 284 ms 39948 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 40776 KB Output is correct
2 Correct 360 ms 46484 KB Output is correct
3 Correct 310 ms 41220 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 58144 KB Output is correct
2 Correct 433 ms 49344 KB Output is correct
3 Correct 559 ms 56420 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 32744 KB Output is correct
2 Correct 436 ms 49412 KB Output is correct
3 Correct 477 ms 51408 KB Output is correct
4 Correct 835 ms 61580 KB Output is correct