Submission #650261

#TimeUsernameProblemLanguageResultExecution timeMemory
650261kingfran1907Traffic (CEOI11_tra)C++17
8 / 100
802 ms92244 KiB
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 1e6+10; const int base = 31337; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int logo = 20; const int off = 1 << logo; const int treesiz = off << 1; int n, m, A, B; int x[maxn], y[maxn]; vector< int > graph[maxn], graph2[maxn]; vector< int > v; int col[maxn]; pair<int, int> dp[maxn]; vector< pair<int, int> > edg; bool bio[maxn]; void add(int a, int b) { graph[a].push_back(b); graph2[b].push_back(a); edg.push_back({a, b}); } void dfs(int x) { col[x] = 1; for (int tren : graph[x]) { if (col[x] == 0) dfs(tren); } v.push_back(x); } void dfs2(int x, int c) { col[x] = c; for (int tren : graph2[x]) if (col[tren] == -1) dfs2(tren, c); } void dfs3(int x) { bio[x] = true; for (int tren : graph[x]) if (!bio[tren]) dfs3(tren); } bool cmp(int a, int b) { return y[a] < y[b]; } pair<int, int> merg(pair<int, int> a, pair<int, int> b) { if (a.X == -1) return b; if (b.X == -1) return a; return {min(a.X, b.X), max(a.Y, b.Y)}; } int main() { scanf("%d%d%d%d", &n, &m, &A, &B); for (int i = 1; i <= n; i++) scanf("%d%d", x+i, y+i); for (int i = 0; i < m; i++) { int a, b, k; scanf("%d%d%d", &a, &b, &k); add(a, b); if (k == 2) add(b, a); } for (int i = 1; i <= n; i++) if (!col[i]) dfs(i); reverse(v.begin(), v.end()); memset(col, -1, sizeof col); vector< int > t; for (int tren : v) { if (col[tren] == -1) { dfs2(tren, tren); t.push_back(tren); } } for (int i = 1; i <= n; i++) graph[i].clear(); for (auto iter : edg) { int x = iter.X; int y = iter.Y; if (col[x] != col[y]) graph[col[x]].push_back(col[y]); } memset(bio, false, sizeof bio); for (int i = 1; i <= n; i++) if (x[i] == 0 && !bio[col[i]]) dfs3(col[i]); vector< int > ed; for (int i = 1; i <= n; i++) { if (x[i] == A && bio[col[i]]) { ed.push_back(i); } } for (int i = 1; i <= n; i++) dp[i] = {-1, -1}; sort(ed.begin(), ed.end(), cmp); for (int i = 0; i < ed.size(); i++) { int tr = col[ed[i]]; dp[tr] = merg(dp[tr], {i, i}); } reverse(t.begin(), t.end()); for (int tren : t) { for (int ac : graph[tren]) dp[tren] = merg(dp[tren], dp[ac]); } ed.clear(); for (int i = 1; i <= n; i++) { if (x[i] == 0) ed.push_back(i); } sort(ed.begin(), ed.end(), cmp); reverse(ed.begin(), ed.end()); for (int tren : ed) { pair<int, int> out = dp[col[tren]]; if (out.X == -1) printf("0\n"); else printf("%d\n", out.Y - out.X + 1); } return 0; }

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < ed.size(); i++) {
      |                  ~~^~~~~~~~~~~
tra.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d%d", &n, &m, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", x+i, y+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
tra.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d%d", &a, &b, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...