Submission #443280

#TimeUsernameProblemLanguageResultExecution timeMemory
443280prvocisloTraffic (CEOI11_tra)C++17
100 / 100
1227 ms74544 KiB
#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 (stderr)

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++)
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...