# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
446835 | 2021-07-23T12:16:09 Z | Nima_Naderi | Traffic (CEOI11_tra) | C++14 | 1384 ms | 98800 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e6 + 5; const double eps = 1e-9; pair<pii,int> X[MAXN]; int ind[MAXN], Y[MAXN]; int vis[MAXN], mrk[MAXN], hi[MAXN], lo[MAXN]; vi adj[MAXN]; vi radj[MAXN]; int main() { int n, m, a, b; ni(n), ni(m), ni(a), ni(b); for (int i = 0; i < n; i++) { ni(X[i].fi.fi), ni(X[i].fi.se); X[i].se = i; Y[i] = X[i].fi.fi; } sort(X, X + n, [](pair<pii,int> lhs, pair<pii,int> rhs) -> bool { if (lhs.fi.fi == rhs.fi.fi) return lhs.fi.se > rhs.fi.se; return lhs.fi.fi < rhs.fi.fi; }); for (int i = 0; i < m; i++) { int c, d, k; ni(c), ni(d), ni(k); c--, d--; adj[c].pb(d), radj[d].pb(c);; if (k == 2) adj[d].pb(c), radj[c].pb(d); } list<int> pq; for (int i = n - 1; i >= 0 && X[i].fi.fi == a; i--) pq.pb(X[i].se), vis[X[i].se] = 1; while (!pq.empty()) { int u = pq.front(); pq.pop_front(); for (int v: radj[u]) if (!vis[v]) { pq.pb(v); vis[v] = 1; } } for (int i = 0; i < n && X[i].fi.fi == 0; i++) if (!vis[X[i].se]) mrk[X[i].se] = 1; // remove from left hand side memset(vis, 0, sizeof vis); for (int i = 0; i < n && X[i].fi.fi == 0; i++) pq.pb(X[i].se), vis[X[i].se] = 1; while (!pq.empty()) { int u = pq.front(); pq.pop_front(); for (int v: adj[u]) if (!vis[v]) { pq.pb(v); vis[v] = 1; } } for (int i = n - 1; i >= 0 && X[i].fi.fi == a; i--) if (!vis[X[i].se]) mrk[X[i].se] = 1; // remove from right hand side int cnt = 0; for (int i = n - 1; i >= 0; i--) { if (mrk[X[i].se] || X[i].fi.fi != a) continue; ind[X[i].se] = cnt++; } memset(vis, 0, sizeof vis); for (int i = 0; i < n && X[i].fi.fi == 0; i++) { if (i > 0) lo[i] = lo[i - 1]; else lo[i] = -1; if (mrk[X[i].se]) continue; pq.pb(X[i].se); while (!pq.empty()) { int u = pq.front(); pq.pop_front(); if (Y[u] == a && (lo[i] == -1 || lo[i] > ind[u])) lo[i] = ind[u]; for (int v: adj[u]) { if (vis[v]) continue; pq.pb(v); vis[v] = 1; } } } memset(vis, 0, sizeof vis); for (int i = n - 1; i >= 0 ; i--) { if (i == n - 1) hi[i] = -1; else hi[i] = hi[i + 1]; if (mrk[X[i].se] || X[i].fi.fi != 0) continue; pq.pb(X[i].se); while (!pq.empty()) { int u = pq.front(); pq.pop_front(); if (Y[u] == a && (hi[i] == -1 || hi[i] < ind[u])) hi[i] = ind[u]; for (int v: adj[u]) { if (vis[v]) continue; pq.pb(v); vis[v] = 1; } } } for (int i = 0; i < n && X[i].fi.fi == 0; i++) { if (mrk[X[i].se]) pri(0); else pri(hi[i] - lo[i] + 1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 51120 KB | Output is correct |
2 | Correct | 29 ms | 51100 KB | Output is correct |
3 | Correct | 31 ms | 51148 KB | Output is correct |
4 | Correct | 31 ms | 51148 KB | Output is correct |
5 | Correct | 31 ms | 51104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 51208 KB | Output is correct |
2 | Correct | 29 ms | 51176 KB | Output is correct |
3 | Correct | 36 ms | 51124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 51136 KB | Output is correct |
2 | Correct | 36 ms | 51148 KB | Output is correct |
3 | Correct | 32 ms | 51144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 51384 KB | Output is correct |
2 | Correct | 35 ms | 51532 KB | Output is correct |
3 | Correct | 35 ms | 51520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 68 ms | 52684 KB | Output is correct |
2 | Correct | 109 ms | 55676 KB | Output is correct |
3 | Correct | 70 ms | 53296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 89 ms | 54696 KB | Output is correct |
2 | Correct | 138 ms | 56712 KB | Output is correct |
3 | Correct | 110 ms | 55244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 192 ms | 57804 KB | Output is correct |
2 | Correct | 207 ms | 59956 KB | Output is correct |
3 | Correct | 296 ms | 64532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 278 ms | 59636 KB | Output is correct |
2 | Correct | 279 ms | 60396 KB | Output is correct |
3 | Correct | 413 ms | 65308 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 364 ms | 64444 KB | Output is correct |
2 | Correct | 401 ms | 67496 KB | Output is correct |
3 | Correct | 683 ms | 77064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 576 ms | 72164 KB | Output is correct |
2 | Correct | 758 ms | 76544 KB | Output is correct |
3 | Correct | 728 ms | 78932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1313 ms | 82856 KB | Output is correct |
2 | Correct | 802 ms | 78608 KB | Output is correct |
3 | Correct | 1197 ms | 94880 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 327 ms | 65968 KB | Output is correct |
2 | Correct | 859 ms | 78740 KB | Output is correct |
3 | Correct | 1031 ms | 89880 KB | Output is correct |
4 | Correct | 1384 ms | 98800 KB | Output is correct |