QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#788666 | #9810. Obliviate, Then Reincarnate | crychic | WA | 3ms | 8880kb | C++20 | 1.7kb | 2024-11-27 17:49:18 | 2024-11-27 17:49:26 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=5e5+5;
vector<pii>e[maxn];
int dfn[maxn],low[maxn],cnt;
int inst[maxn],scc[maxn],sc;
int fl[maxn],ans[maxn];
vector<int>ins[maxn],stk;
void dfs(int x){
dfn[x]=low[x]=++cnt;
inst[x]=1;
stk.push_back(x);
for(auto t:e[x]){
int u=t.first;
if(!dfn[u]){
dfs(u);
low[x]=min(low[x],low[u]);
}
else if(inst[u])low[x]=min(low[x],dfn[u]);
}
if(low[x]==dfn[x]){
sc++;
while(1){
int u=stk.back();
inst[u]=0;
scc[u]=sc;
ins[sc].push_back(u);
stk.pop_back();
if(u==x)break;
}
}
}
ll dis[maxn];
int vis[maxn],T;
void dfs2(int x){
vis[x]=1;
for(auto t:e[x]){
int u=t.first,w=t.second;
if(scc[u]!=scc[x])continue;
if(vis[u]){
if(dis[u]!=dis[x]+w)fl[T]=1;
continue;
}
dis[u]=dis[x]+w;
dfs2(u);
}
}
void dfs3(int x){
if(vis[x])return;
vis[x]=1;
for(auto t:e[x]){
int u=t.first;
dfs3(u);
ans[x]|=ans[u];
}
}
void solve(){
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>w;
u=(u%n+n)%n+1;
v=((u+w)%n+n)%n+1;
e[u].push_back({v,w});
// cout<<u<<" "<<v<<" "<<w<<"\n";
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i);
}
}
for(int i=1;i<=sc;i++){
T=i;
dfs2(ins[i][0]);
if(fl[i]){
for(auto u:ins[i]){
ans[u]=1;
}
}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
dfs3(i);
}
for(int i=1;i<=q;i++){
int x;
cin>>x;
x=(x%n+n)%n+1;
if(ans[x])cout<<"Yes\n";
else cout<<"No\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 8880kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
No No No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'