oj.uz

Submission #958282

# Submission time Handle Problem Language Result Execution time Memory
958282 2024-04-05T09:53:46 Z Lithanium Traffic (CEOI11_tra) C++17
100 / 100
 1335 ms 69312 KB 
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> leftSide, rightSide;
vector<int> adj[300005], rev[300005];
int loc[300005][2], pos[300005], temp, a, b;
bool seen[300005], dead[300005];
int ans[300005][2]; //North South

void dfs(int n) {
    seen[n] = 1;
    for (int i:adj[n]) if (!seen[i]) dfs(i);
}

void dfs2(int n) {
    seen[n] = 1;
    for (int i:rev[n]) if (!seen[i]) dfs2(i);
}

void solve(int n, bool north) {
    seen[n] = 1;
    if (loc[n][0] == a) {
        if (!north) temp = max(temp, pos[n]);
        else temp = min(temp, pos[n]);
    }
    for (int i:adj[n]) if (!seen[i]) solve(i, north);
}

int main() {
    int n, m;
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i ++) {
        cin >> loc[i][0] >> loc[i][1];
        if (loc[i][0] == 0) {
            leftSide.push_back({loc[i][1], i});
        } else if (loc[i][0] == a) {
            rightSide.push_back({loc[i][1], i});
        }
    }
    while (m --) {
        int a1, b1, c1;
        cin >> a1 >> b1 >> c1;
        adj[a1].push_back(b1);
        rev[b1].push_back(a1);
        if (c1 == 2) {adj[b1].push_back(a1); rev[a1].push_back(b1);}
    }
    sort(leftSide.begin(), leftSide.end());
    sort(rightSide.begin(), rightSide.end());
    for (auto[x, y]:leftSide) if (!seen[y]) dfs(y);
    for (int i = 1; i <= n; i ++) if (loc[i][0] == a and !seen[i]) dead[i] = 1;
    memset(seen, 0, sizeof(seen));
    for (auto[x, y]:rightSide) if (!seen[y]) dfs2(y);
    //for (int i = 1; i <= n; i ++) cout << seen[i] << " ";
    for (int i = 0; i <= n; i ++) if (loc[i][0] == 0 and !seen[i]) dead[i] = 1;
    int ptr = 1;
    for (int i = 0; i < rightSide.size(); i ++) {
        auto[x, y] = rightSide[i];
        if (!dead[y]) {
            pos[y] = ptr;
            ptr ++;
        }
    }
    // South Side
    memset(seen, 0, sizeof(seen));
    for (auto[x, y]:leftSide) if (!dead[y]) {
        solve(y, 0);
        ans[y][1] = temp;
    }
    // North Side
    memset(seen, 0, sizeof(seen));
    temp = 1e9;
    reverse(leftSide.begin(), leftSide.end());
    for (auto[x, y]:leftSide) if (!dead[y]) {
        solve(y, 1);
        ans[y][0] = temp;
    }
    //for (int i = 1; i <= n; i ++) cout << dead[i] << " ";
    //cout << "\n";
    for (auto[x, y]:leftSide) {
        if (dead[y]) cout << "0\n";
        else cout << ans[y][1] - ans[y][0] + 1 << "\n";
    }
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:56: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]
   56 |     for (int i = 0; i < rightSide.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16472 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 4 ms 16476 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 10 ms 16988 KB Output is correct
3 Correct 9 ms 16984 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 21840 KB Output is correct
2 Correct 72 ms 25548 KB Output is correct
3 Correct 43 ms 23124 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 24252 KB Output is correct
2 Correct 93 ms 27084 KB Output is correct
3 Correct 64 ms 25124 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 27020 KB Output is correct
2 Correct 167 ms 32152 KB Output is correct
3 Correct 231 ms 31824 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 29912 KB Output is correct
2 Correct 159 ms 31308 KB Output is correct
3 Correct 262 ms 32600 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 34612 KB Output is correct
2 Correct 316 ms 38400 KB Output is correct
3 Correct 544 ms 42292 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 42200 KB Output is correct
2 Correct 601 ms 50500 KB Output is correct
3 Correct 648 ms 43484 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 59424 KB Output is correct
2 Correct 631 ms 51832 KB Output is correct
3 Correct 1144 ms 58152 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 34372 KB Output is correct
2 Correct 716 ms 56432 KB Output is correct
3 Correct 924 ms 52916 KB Output is correct
4 Correct 1335 ms 69312 KB Output is correct