QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788714 | #9810. Obliviate, Then Reincarnate | Maxduan | RE | 604ms | 36004kb | C++20 | 2.0kb | 2024-11-27 18:01:08 | 2024-11-27 18:01:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int long long
#define ll 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];
bool ok[maxn];
bool 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;
}
}
}
ll dp[maxn],nows;
void dfs1(int u){
vis[u]=1;
for(auto [w,v]:g[u]){
if(scc[v]!=nows)continue;
if(vis[v]){
if(dp[v]!=dp[u]+w){
ok[nows]=1;
}
}
else{
dp[v]=dp[u]+w;
dfs1(v);
}
}
}
void dfs2(int u){
vis[u]=1;
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;
g[a].push_back({b,nxt});
}
for(int i=0;i<n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=0;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=0;i<n;i++){
if(vis[i])continue;
nows=scc[i];
dfs1(i);
}
memset(vis,0,sizeof(vis));
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: 10000kb
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: 12000kb
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: 2ms
memory: 10196kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9792kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: 0
Accepted
time: 604ms
memory: 36004kb
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...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 500000 tokens
Test #6:
score: -100
Runtime Error
input:
100848 500000 500000 720352587 361776806 231853504 -933882325 960971230 -83519300 -152772415 -631132247 842871215 -666621297 857194330 -754943024 -698506963 -705416545 -3551931 -927937446 628710320 -942247987 674921043 847145884 -325629529 475694308 -339363446 686789318 236702996 654762989 420412365...