Submission #889650

#	Time	Username	Problem	Language	Result	Execution time	Memory
889650		rxlfd314	Traffic (CEOI11_tra)	C++17	100 / 100	739 ms	61136 KiB

tra

#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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9