QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787313#9810. Obliviate, Then ReincarnateUESTC_OldEastWest#TL 171ms29096kbC++203.8kb2024-11-27 11:04:312024-11-27 11:04:32

Judging History

This is the latest submission verdict.

  • [2024-11-27 11:04:32]
  • Judged
  • Verdict: TL
  • Time: 171ms
  • Memory: 29096kb
  • [2024-11-27 11:04:31]
  • Submitted

answer

#include <bits/stdc++.h>
const long long INF = 1e16;

namespace SPFA {
  int n;
  std::vector<int> cnt, vis, in_s;
  std::vector<long long> dis;
  std::vector<std::vector<std::pair<int, int> > > G;

  void Init(int _n, std::vector<std::vector<std::pair<int, int> > > _G) {
    n = _n, G = _G;
    dis = std::vector<long long> (n, INF);
    cnt = vis = in_s = std::vector<int> (n);
  }

  bool SPFA(std::vector<int> &s, int coef) {
    if (s.empty()) return false;
    // std::cout << "Begin" << std::endl;

    for (int u : s) in_s[u] = 1;
    int st = s[0];
    dis[st] = 0, vis[st] = 1;
    int head = 0, tail = 1;
    std::vector<int> que(1, st);
    bool neg_circle = false;
    while (head < tail) {
      int u = que[head++];
      vis[u] = 0;
      for (auto [v, w] : G[u]) {
        if (!in_s[v]) continue;
        w *= coef;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          cnt[v] = cnt[u] + 1;
          if (cnt[v] >= n) {neg_circle = true; break;}
          if (!vis[v]) que.emplace_back(v), ++tail, vis[v] = 1;
        }
      }
    }
    for (int u : s) dis[u] = INF, cnt[u] = vis[u] = in_s[u] = 0;

    // std::cout << "End" << std::endl;

    return neg_circle;
  }
}

void charming() {
  int n, m, q; std::cin >> n >> m >> q;
  std::vector<std::vector<std::pair<int, int> > > G(n);
  for (int i = 0, a, b, c; i < m; ++i) {
    std::cin >> a >> b;
    a = ((a % n) + n) % n;
    c = (((a + b) % n) + n) % n;
    G[a].emplace_back(std::make_pair(c, b));

    // std::cout << "G Add Edge " << a << ' ' << c << ' ' << b << '\n';
  }

  int tot = 0, scc_cnt = 0;
  std::vector<int> dfn(n, -1), low(n, -1), bel(n, -1), stk;
  std::vector<std::vector<int> > scc;
  auto Tarjan = [&](auto &&self, int u) -> void {
    dfn[u]= low[u] = tot++;
    stk.emplace_back(u);
    for (auto [v, _] : G[u]) {
      if (dfn[v] == -1) {
        self(self, v);
        low[u] = std::min(low[u], low[v]);
      } else if (bel[v] == -1) low[u] = std::min(low[u], dfn[v]);
    }
    if (low[u] >= dfn[u]) {
      bel[u] = scc_cnt;
      std::vector<int> new_scc;
      while (stk.back() != u) {
        bel[stk.back()] = scc_cnt;
        new_scc.emplace_back(stk.back());
        stk.pop_back();
      }
      new_scc.emplace_back(u);
      stk.pop_back();
      scc.emplace_back(new_scc);
      ++scc_cnt;
    }
  };
  for (int u = 0; u < n; ++u) if (dfn[u] == -1) Tarjan(Tarjan, u);

  // for (int i = 0; i < n; ++i) std::cout << bel[i] << ' ';
  // std::cout << '\n';

  // std::cout << 0 << std::endl;

  std::vector<int> du(scc_cnt);
  std::vector<std::vector<int> > nG(scc_cnt);
  for (int u = 0; u < n; ++u) {
    for (auto [v, _] : G[u]) {
      if (bel[u] != bel[v]) {
        // std::cout << "nG Add edge " << ' ' << bel[v] << ' ' << bel[u] << std::endl;
        nG[bel[v]].emplace_back(bel[u]);
        ++du[bel[u]];
      }
    }
  }

  SPFA::Init(n, G);
  auto Check = [&](int id) -> bool {
    // std::cout << id << ' ' << SPFA::SPFA(scc[id], 1) << ' ' << SPFA::SPFA(scc[id], -1) << '\n';
    return SPFA::SPFA(scc[id], 1) | SPFA::SPFA(scc[id], -1);
  };

  // std::cout << 1 << std::endl;

  int head = 0, tail = 0;
  std::vector<int> que, f(n);
  for (int u = 0; u < scc_cnt; ++u) if (!du[u]) que.emplace_back(u), ++tail;
  while (head < tail) {
    int u = que[head++];
    if (!f[u]) f[u] |= Check(u);
    for (int v : nG[u]) {
      --du[v];
      f[v] |= f[u];
      if (!du[v]) que.emplace_back(v), ++tail;
    }
  }

  // std::cout << 2 << std::endl;

  for (int i = 0, x; i < q; ++i) {
    std::cin >> x;
    x = ((x % n) + n) % n;
    x = bel[x];
    if (f[x]) std::cout << "Yes\n";
    else std::cout << "No\n";
  }
}

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  charming();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

Yes
Yes
No

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 171ms
memory: 29096kb

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 500000 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

output:


result: