Submission #889650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889650	2023-12-20T04:28:29 Z	rxlfd314	Traffic (CEOI11_tra)	C++17	100 / 100	739 ms	61136 KB

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;

#define vt vector
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
void solve();

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int T = 1;
  //cin >> T;
  FOR(t, 1, T) {
    solve();
  }
}

void solve() {
  int N, M, A, B;
  cin >> N >> M >> A >> B;
  int X[N], Y[N];
  vt<int> vw, ve;
  FOR(i, 0, N-1) {
    cin >> X[i] >> Y[i];
    if (X[i] == 0)
      vw.push_back(i);
    if (X[i] == A)
      ve.push_back(i);
  }
  sort(all(vw), [&](const int &a, const int &b) {
    return Y[a] < Y[b];
  });
  sort(all(ve), [&](const int &a, const int &b) {
    return Y[a] < Y[b];    
  });
  vt<vt<int>> adj(N), radj(N);
  FOR(_, 1, M) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[--a].push_back(--b);
    radj[b].push_back(a);
    if (c == 2) {
      adj[b].push_back(a);
      radj[a].push_back(b);
    }
  }
  {
    queue<int> qu;
    bool seen[N] = {};
    for (int i : vw) {
      seen[i] = true;
      qu.push(i);
    }
    while (size(qu)) {
      int i = qu.front();
      qu.pop();
      for (int j : adj[i])
        if (!seen[j]) {
          seen[j] = true;
          qu.push(j);
        }
    }
    vt<int> nve;
    for (int i : ve)
      if (seen[i])
        nve.push_back(i);
    ve = nve;
  }
  vt<int> L(N, -2e9), R(N, -2e9);
  auto dijk = [&](vt<int> &V, vt<int> &sts, vt<vt<int>> &G, int mul) {
    priority_queue<ari2> pq;
    for (int i : sts) {
      V[i] = Y[i] * mul;
      pq.push({V[i], i});
    }
    while (size(pq)) {
      auto [d, i] = pq.top();
      pq.pop();
      if (d < V[i])
        continue;
      for (int j : G[i])
        if (d > V[j])
          pq.push({V[j] = d, j});
    }
  };
  dijk(L, ve, radj, -1);
  dijk(R, ve, radj, 1);
  int l = 0, r = 0;
  vt<int> ans;
  for (int i : vw) {
    L[i] *= -1;
    if (L[i] == 2e9)
      ans.push_back(0);
    else {
      while (l < size(ve) && Y[ve[l]] < L[i])
        l++;
      while (r < size(ve) && Y[ve[r]] <= R[i])
        r++;
      ans.push_back(r - l);
    }
  }
  reverse(all(ans));
  for (int i : ans)
    cout << i << '\n';
}

Subtask #1
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	452 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	3 ms	1116 KB	Output is correct
3	Correct	3 ms	860 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3932 KB	Output is correct
2	Correct	38 ms	7820 KB	Output is correct
3	Correct	18 ms	4156 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	6748 KB	Output is correct
2	Correct	52 ms	9624 KB	Output is correct
3	Correct	24 ms	7528 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	13056 KB	Output is correct
2	Correct	74 ms	15848 KB	Output is correct
3	Correct	94 ms	17560 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	15816 KB	Output is correct
2	Correct	97 ms	15940 KB	Output is correct
3	Correct	119 ms	18484 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	25576 KB	Output is correct
2	Correct	189 ms	29172 KB	Output is correct
3	Correct	234 ms	33468 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	40836 KB	Output is correct
2	Correct	335 ms	45520 KB	Output is correct
3	Correct	285 ms	36420 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	644 ms	58176 KB	Output is correct
2	Correct	380 ms	47152 KB	Output is correct
3	Correct	510 ms	56072 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	32796 KB	Output is correct
2	Correct	395 ms	49060 KB	Output is correct
3	Correct	409 ms	50512 KB	Output is correct
4	Correct	739 ms	61136 KB	Output is correct

Submission #889650

Compilation message