QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#811391 | #9810. Obliviate, Then Reincarnate | rotcar07 | RE | 2ms | 7732kb | C++23 | 1.2kb | 2024-12-12 19:01:07 | 2024-12-12 19:01:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,Q;typedef long long ll;
int ins[N],dfn[N],toki,low[N],col[N],tot;ll h[N];
vector<pair<int,int>> e[N];stack<int> st;
void dfs(int p){
dfn[p]=low[p]=++toki;ins[p]=1;st.push(p);
for(auto [x,y]:e[p]) low[p]=min(low[p],dfn[x]?ins[x]?dfn[x]:int(1e9):(h[x]=h[p]+y,dfs(x),low[x]));
if(dfn[p]==low[p]){
col[p]=++tot;ins[p]=0;
while(!st.empty()&&st.top()!=p) col[st.top()]=tot,ins[st.top()]=0,st.pop();
st.pop();
}
}
bool f[N];
vector<int> g[N];int deg[N];
int main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>Q;
for(int i=1,a,b;i<=m;i++) cin>>a>>b,a=(a%n+n)%n,e[a].emplace_back(((a+b)%n+n)%n,b);
for(int i=0;i<n;i++) if(!dfn[i]) dfs(i);
for(int i=0;i<n;i++)
for(auto [x,y]:e[i]){
if(col[i]==col[x]){
if(h[i]+y!=h[x]) f[col[i]]=1;
}
else g[col[x]].push_back(col[i]),deg[col[i]]++;
}
queue<int> q;
for(int i=1;i<=tot;i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int p=q.front();q.pop();
for(int x:g[p]){
f[x]|=f[p];
if(!--deg[x]) q.push(x);
}
}
while(Q--){
int x;cin>>x;
puts(f[col[x]]?"Yes":"No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7660kb
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: 2ms
memory: 7732kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: -100
Runtime Error
input:
1 1 1 0 1000000000 -1000000000