# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
446835 | Nima_Naderi | Traffic (CEOI11_tra) | C++14 | 1384 ms | 98800 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |