QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782463 | #9810. Obliviate, Then Reincarnate | dreamjoker | WA | 0ms | 3880kb | C++23 | 2.3kb | 2024-11-25 20:09:00 | 2024-11-25 20:09:01 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 20:09:00]
- Submitted
answer
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using pii = pair<ll,ll>;
const ll inf = numeric_limits<ll>::max()>>1;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n,m,Q; cin>>n>>m>>Q;
vector<vector<pii>> e(n+1);
for(int i=0;i<m;i++) {
int u,v,w; cin>>u>>w;
v=((u+w)%n+n)%n;
u=(u%n+n)%n;
e[u].push_back({w,v});
}
vector<int> dfn(n+1),low(n+1),instk(n+1),scc(n+1);
int cur=0,tot=0;
vector<vector<int>> st;
stack<int> stk;
auto tarjan=[&](auto &&self,int x)->void {
dfn[x]=low[x]=++cur;
stk.push(x); instk[x]=1;
for(auto [w,y]:e[x]) {
if(!dfn[y]) {
self(self,y);
low[x]=min(low[x],low[y]);
} else if(instk[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]) {
st.push_back({}); auto &v=st.back();
int y;
do {
y=stk.top(); stk.pop();
instk[y]=0;
v.push_back(y);
scc[y]=tot;
} while(y!=x);
tot++;
}
};
for(int i=0;i<n;i++) {
if(!dfn[i]) tarjan(tarjan,i);
}
vector<int> vis(n+1);
vector<ll> h(n+1);
auto judge=[&](auto &&self,int x,ll dis)->bool {
h[x]=dis; vis[x]=1;
for(auto [w,y]:e[x]) if(scc[y]==scc[x]) {
if(!vis[y]) {if(!self(self,y,h[x]+w)) return true;}
else if(h[y]!=h[x]+w) return true;
}
return false;
};
vector<int> flag(n+1);
for(int i=0;i<tot;i++) {
for(int x:st[i]) {
for(auto [w,y]:e[x]) {
if(flag[scc[y]]) {
flag[i]=1;
break;
}
if(y==x&&w!=0) {
flag[i]=1;
break;
}
}
if(flag[i]) break;
}
if(!flag[i]) flag[i]|=judge(judge,st[i].back(),0);
}
while(Q--) {
int x; cin>>x;
x=(x%n+n)%n;
cout<<(flag[scc[x]]?"Yes":"No")<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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: 3572kb
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: 3880kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3640kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No Yes No
result:
wrong answer 2nd words differ - expected: 'No', found: 'Yes'