oj.uz

Submission #443280

# Submission time Handle Problem Language Result Execution time Memory
443280 2021-07-10T09:27:31 Z prvocislo Traffic (CEOI11_tra) C++17
100 / 100
 1227 ms 74544 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 3e5 + 5;
vector<int> g[maxn], gr[maxn], kedy[maxn], w, e;
void add_edge(int u, int v) { g[u].push_back(v), gr[v].push_back(u); }
int ok[maxn], vis[maxn], x[maxn], y[maxn], ans[maxn], n, m, a, b;
bool is_w(int u) { return x[u] == 0; }
bool is_e(int u) { return x[u] == a; }
void dfsr(int u)
{
    ok[u] = true;
    for (int v : gr[u]) if (!ok[v]) dfsr(v);
}
void dfs(int u, int od)
{
    vis[u] = true;
    if (is_e(u)) kedy[u].push_back(od);
    for (int v : g[u]) if (!vis[v]) dfs(v, od);
}
bool cmp(int i, int j) { return y[i] > y[j]; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> m >> a >> b;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        if (is_w(i)) w.push_back(i);
        if (is_e(i)) e.push_back(i);
    }
    sort(w.begin(), w.end(), cmp);
    for (int i = 0, u, v, k; i < m; i++)
    {
        cin >> u >> v >> k; u--, v--;
        add_edge(u, v);
        if (k == 2) add_edge(v, u);
    }
    for (int i : e) dfsr(i);
    for (int i = 0; i < w.size(); i++) dfs(w[i], i);
    memset(vis, 0, sizeof(vis));
    for (int i = w.size()-1; i >= 0; i--) dfs(w[i], i);
    for (int i : e) if (kedy[i].size()) ans[kedy[i][0]]++, ans[kedy[i][1]+1]--;
    for (int i = 0; i < w.size(); i++)
    {
        if (i) ans[i] += ans[i-1];
        cout << (ok[w[i]] ? ans[i] : 0) << "\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22604 KB Output is correct
2 Correct 15 ms 22604 KB Output is correct
3 Correct 16 ms 22604 KB Output is correct
4 Correct 16 ms 22548 KB Output is correct
5 Correct 16 ms 22604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22568 KB Output is correct
2 Correct 18 ms 22604 KB Output is correct
3 Correct 17 ms 22604 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22612 KB Output is correct
2 Correct 17 ms 22596 KB Output is correct
3 Correct 16 ms 22604 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22812 KB Output is correct
2 Correct 23 ms 23132 KB Output is correct
3 Correct 23 ms 22944 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24020 KB Output is correct
2 Correct 93 ms 28284 KB Output is correct
3 Correct 47 ms 25180 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26416 KB Output is correct
2 Correct 113 ms 30044 KB Output is correct
3 Correct 82 ms 27540 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 29992 KB Output is correct
2 Correct 179 ms 35420 KB Output is correct
3 Correct 294 ms 34780 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 32820 KB Output is correct
2 Correct 198 ms 34736 KB Output is correct
3 Correct 295 ms 35448 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 38480 KB Output is correct
2 Correct 352 ms 43704 KB Output is correct
3 Correct 573 ms 46332 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 47448 KB Output is correct
2 Correct 565 ms 57092 KB Output is correct
3 Correct 568 ms 47812 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 64520 KB Output is correct
2 Correct 656 ms 59564 KB Output is correct
3 Correct 1047 ms 63252 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 39584 KB Output is correct
2 Correct 692 ms 62448 KB Output is correct
3 Correct 888 ms 58064 KB Output is correct
4 Correct 1227 ms 74544 KB Output is correct