QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#885669 | #9810. Obliviate, Then Reincarnate | furrywolf | RE | 1ms | 14056kb | C++20 | 1.6kb | 2025-02-06 17:04:04 | 2025-02-06 17:04:12 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define R register int
#define if(x) if(__builtin_expect(x,1))
#define while(x) while(__builtin_expect(x,1))
using namespace std;
const int N=5e5+1;
int n,m,q;
struct node{int to,nxt,w;}e[N];
int head[N],dfn[N],low[N],tot,ts,dep[N];
bool vis[N],ans[N];stack<int>s;
void add(int u,int v,int w){e[++tot]={v,head[u],w};head[u]=tot;}
void tarjan(int u){
dfn[u]=low[u]=++ts;s.push(u);vis[u]=1;
for(R i=head[u]; i; i=e[i].nxt){
int v=e[i].to;
if(dfn[v]==-1)dep[v]=dep[u]+e[i].w,tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v]){
if(dep[u]-dep[v]+e[i].w!=0)ans[u]=1;
low[u]=min(low[u],dfn[v]);
}
ans[u]|=ans[v];
}
if(low[u]==dfn[u]){
vector<int>v;v.clear();
int now=ans[u];
while(s.top()!=u){
vis[s.top()]=0;
v.push_back(s.top());
now|=ans[s.top()];
s.pop();
}
s.pop();vis[u]=0;
for(auto i:v)ans[i]=now;
}
}
int main(){
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
memset(low,-1,sizeof low);
memset(dfn,-1,sizeof dfn);
cin>>n>>m>>q;
for(R i=1,u,v; i<=m; i++)
cin>>u>>v,add((u%n+n)%n,((u+v)%n+n)%n,v);
for(R i=0; i<n; i++)
if(dfn[i]==-1)tarjan(i);
// for(R i=1; i<=n; i++)cout<<dfn[i]<<' ';cout<<'\n';
// for(R i=1; i<=n; i++)cout<<low[i]<<' ';cout<<'\n';
while(q--){
int x;cin>>x;
cout<<(ans[(x+n)%n]?"Yes":"No")<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 12000kb
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: 11832kb
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: 12004kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 14056kb
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...