QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#810134 | #9810. Obliviate, Then Reincarnate | snowysecret | RE | 8ms | 15572kb | C++20 | 3.4kb | 2024-12-11 19:57:11 | 2024-12-11 19:57:11 |
Judging History
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...