QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788674 | #9810. Obliviate, Then Reincarnate | Maxduan | WA | 3ms | 11788kb | C++20 | 2.2kb | 2024-11-27 17:50:05 | 2024-11-27 17:50:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int long long
#define pii pair<int,int>
vector<pii>g[maxn],g2[maxn];
stack<int>st;
int dn,dfn[maxn],low[maxn];
int scc[maxn],cnt;
bool instk[maxn];
int ok[maxn];
int vis[maxn];
void tarjan(int k)
{
dfn[k]=low[k]=++dn;
st.push(k),instk[k]=1;
for(auto [len,x]:g[k])
{
if(!dfn[x])
{
tarjan(x);
low[k]=min(low[k],low[x]);
}
else if(dfn[x]&&instk[x]) low[k]=min(low[k],dfn[x]);
}
if(dfn[k]==low[k])
{
cnt++;
while(1)
{
int temp=st.top();
st.pop();
instk[temp]=0;
scc[temp]=cnt;
if(temp==k)break;
}
}
}
int dp[maxn],nows;
void dfs1(int u){
for(auto [w,v]:g[u]){
if(scc[v]!=nows)continue;
if(dp[v]!=-1){
//cout<<"u v w dp="<<u<<' '<<v<<' '<<w<<' '<<dp[u]<<' '<<dp[v]<<'\n';
if(dp[v]!=dp[u]+w){
ok[nows]=1;
}
}
else{
dp[v]=dp[u]+w;
dfs1(v);
}
}
}
void dfs2(int u){
for(auto [w,v]:g2[u]){
if(!vis[v])dfs2(v);
if(ok[v])ok[u]=1;
}
}
signed main(){
int n,m,q;cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
a=(a%n+n)%n;
int nxt=(a+b)%n;
//cout<<"a nxt"<<' '<<a<<' '<<nxt<<'\n';
g[a].push_back({b,nxt});
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++){
for(auto [w,v]:g[i]){
if(scc[i]==scc[v])continue;
g2[scc[i]].push_back({w,scc[v]});
}
}
for(int i=1;i<=n;i++){
dp[i]=-1;
//cout<<"i scc="<<i<<' '<<scc[i]<<'\n';
}
for(int i=1;i<=n;i++){
if(dp[i]!=-1)continue;
nows=scc[i];
dp[i]=0;
dfs1(i);
}
for(int i=1;i<=cnt;i++){
if(!vis[i])dfs2(i);
}
for(int i=1;i<=q;i++){
int x;cin>>x;
x=(x%n+n)%n;
if(ok[scc[x]]){
cout<<"Yes\n";
}
else cout<<"No\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11788kb
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: 3ms
memory: 9964kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 9764kb
input:
1 1 1 0 1000000000 -1000000000
output:
No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'