QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810134#9810. Obliviate, Then ReincarnatesnowysecretRE 8ms15572kbC++203.4kb2024-12-11 19:57:112024-12-11 19:57:11

Judging History

This is the latest submission verdict.

  • [2024-12-11 19:57:11]
  • Judged
  • Verdict: RE
  • Time: 8ms
  • Memory: 15572kb
  • [2024-12-11 19:57:11]
  • Submitted

answer

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 5e5 + 10, MOD = 1e9 + 7, HASHMOD = 1734232211;
int fac[MAXN], invfac[MAXN];
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) { return uniform_int_distribution<int>(x, y)(rng); }
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { return bm(b, MOD-2); }
vector<int> prefix_function(vector<int> t) {
  int n = t.size(); vector<int> lps(n, 0);
  for(int i=1; i<n; i++) {
    int j = lps[i-1]; while(j > 0 && t[i] != t[j]) j = lps[j-1];
    lps[i] = (t[i] == t[j] ? j+1 : 0); 
  } return lps;
}
int nCr(int n, int r) {
  return (((fac[n] * invfac[r]) % MOD) * invfac[n-r]) % MOD;
}
void precomp() {
  for(int i=0; i<MAXN; i++) fac[i] = (i ? (fac[i-1] * i) % MOD : 1);
  invfac[MAXN - 1] = inv(fac[MAXN - 1]);
  for(int i=MAXN-2; i>=0; i--) invfac[i] = (invfac[i+1] * (i+1)) % MOD;
}
vector<pair<int, int> > adj[MAXN];
vector<pair<int, int> > rev[MAXN];
bool vis[MAXN];
stack<int> ts;
void dfs1(int node) {
  vis[node] = 1;
  for(pair<int, int> x: adj[node]) {
    if(!vis[x.first]) {
      dfs1(x.first);
    }
  }
  ts.push(node);
}
vector<int> scc;
bool in[MAXN], in2[MAXN];
void dfs2(int node) {
  vis[node] = 1;
  in[node] = in2[node] = 1;
  for(pair<int, int> x: rev[node]) {
    if(!vis[x.first]) {
      dfs2(x.first);
    }
  }
  scc.push_back(node);
}
int weight[MAXN];
void dfs3(int node, int val) {
  weight[node] = val;
  in[node] = 0;
  for(pair<int, int> x: adj[node]) {
    if(in[x.first]) {
      dfs3(x.first, val + x.second);
    }
  }
}
void solve(int tc) {
  int n, m, q;
  cin >> n >> m >> q;
  for(int i=0; i<m; i++) {
    int a, b;
    cin >> a >> b;
    a %= n;
    if(a < 0) a += n;
    adj[a].push_back({(a+b) % n, b});
    rev[(a+b) % n].push_back({a, b});
  }
  for(int i=0; i<n; i++) {
    if(!vis[i]) {
      dfs1(i);
    }
  }
  for(int i=0; i<n; i++) vis[i] = 0;
  bool ans[n];
  for(int i=0; i<n; i++) ans[i] = 0;
  while(!ts.empty()) {
    int t = ts.top();
    ts.pop();
    if(!vis[t]) {
      scc.clear();
      dfs2(t);
      dfs3(scc[0], scc[0]);
      bool nonzero = 0;
      for(int x: scc) {
        for(pair<int, int> y: adj[x]) {
          if(!in2[y.first]) continue;
          if(weight[x] + y.second != weight[y.first]) {
            nonzero = 1;
          }
        }
      }
      if(nonzero) {
        for(int q: scc) ans[q] = 1;
      }
      for(int x: scc) in2[x] = 0;
    }
  }
  queue<int> que;
  for(int i=0; i<n; i++) vis[i] = 0;
  for(int i=0; i<n; i++) {
    if(ans[i]) que.push(i);
  }
  while(que.size()) {
    int f = que.front();
    que.pop();
    if(!vis[f]) {
      vis[f] = 1;
      ans[f] = 1;
      for(pair<int, int> x: rev[f]) {
        if(!vis[x.first]) {
          que.push(x.first);
        }
      }
    }
  }
  while(q--) {
    int x;
    cin >> x;
    x %= n;
    if(x < 0) x += n;
    cout << (ans[x] ? "Yes\n" : "No\n");
  }
}
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
g++ -Wl,-stack_size,0x20000000 code2.cpp -std=c++17 -O2 -o code2
./code2 < input.txt
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 15572kb

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: 8ms
memory: 14892kb

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: 8ms
memory: 15040kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 8ms
memory: 14944kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Runtime Error

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:


result: