| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 127107 | 2019-07-08T22:30:53 Z | eriksuenderhauf | Traffic (CEOI11_tra) | C++11 | 1438 ms | 98964 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 | 49 ms | 51320 KB | Output is correct |
| 2 | Correct | 48 ms | 51192 KB | Output is correct |
| 3 | Correct | 49 ms | 51192 KB | Output is correct |
| 4 | Correct | 48 ms | 51192 KB | Output is correct |
| 5 | Correct | 49 ms | 51320 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 48 ms | 51320 KB | Output is correct |
| 2 | Correct | 49 ms | 51244 KB | Output is correct |
| 3 | Correct | 49 ms | 51320 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 49 ms | 51192 KB | Output is correct |
| 2 | Correct | 49 ms | 51320 KB | Output is correct |
| 3 | Correct | 50 ms | 51292 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 62 ms | 51448 KB | Output is correct |
| 2 | Correct | 56 ms | 51832 KB | Output is correct |
| 3 | Correct | 55 ms | 51676 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 75 ms | 53368 KB | Output is correct |
| 2 | Correct | 126 ms | 57128 KB | Output is correct |
| 3 | Correct | 111 ms | 54060 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 117 ms | 56200 KB | Output is correct |
| 2 | Correct | 154 ms | 58620 KB | Output is correct |
| 3 | Correct | 120 ms | 56756 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 181 ms | 60308 KB | Output is correct |
| 2 | Correct | 240 ms | 63256 KB | Output is correct |
| 3 | Correct | 352 ms | 64760 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 299 ms | 63328 KB | Output is correct |
| 2 | Correct | 277 ms | 63528 KB | Output is correct |
| 3 | Correct | 360 ms | 65576 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 408 ms | 70220 KB | Output is correct |
| 2 | Correct | 427 ms | 73592 KB | Output is correct |
| 3 | Correct | 722 ms | 77064 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 632 ms | 81272 KB | Output is correct |
| 2 | Correct | 755 ms | 86664 KB | Output is correct |
| 3 | Correct | 757 ms | 79096 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1279 ms | 97712 KB | Output is correct |
| 2 | Correct | 956 ms | 89096 KB | Output is correct |
| 3 | Correct | 1235 ms | 94996 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 398 ms | 73216 KB | Output is correct |
| 2 | Correct | 925 ms | 89800 KB | Output is correct |
| 3 | Correct | 1029 ms | 89976 KB | Output is correct |
| 4 | Correct | 1438 ms | 98964 KB | Output is correct |