QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794384#9810. Obliviate, Then Reincarnateucup-team3161#WA 289ms104708kbC++171.5kb2024-11-30 14:00:052024-11-30 14:00:13

Judging History

This is the latest submission verdict.

  • [2024-11-30 14:00:13]
  • Judged
  • Verdict: WA
  • Time: 289ms
  • Memory: 104708kb
  • [2024-11-30 14:00:05]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define eb emplace_back
const int N=1e6+5;
int n,m,c,dfn[N],low[N],st[N],bl[N];
ll s[N];bool vs[N],tg[N];
vector<int> e2[N];
vector<pii> e[N],e1[N];
void dfs(int u,ll s1)
{
    if(vs[u])
    {
        if(s[u]!=s1) tg[bl[u]]=1;
        return;
    }
    vs[u]=1;s[u]=s1;
    for(auto [v,w]:e[u]) if(bl[u]==bl[v]) dfs(v,s1+w);
    for(auto [v,w]:e1[u]) if(bl[u]==bl[v]) dfs(v,s1+w);
}
void Tarjan(int u)
{
    dfn[u]=low[u]=++dfn[0];
    st[++st[0]]=u;
    for(auto [v,w]:e[u])
        if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
        else if(!bl[v]) low[u]=min(low[u],dfn[v]);
    if(dfn[u]==low[u])
    {
        bl[++bl[0]]=u;
        while(st[st[0]]!=u) bl[st[st[0]--]]=bl[0];--st[0];    
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&c);
    for(int i=1,u,v,x;i<=m;++i)
    {
        scanf("%d %d",&u,&x);
        u=(u%n+n)%n;
        v=((u+x)%n+n)%n;
        ++u;++v;
        e[u].eb(v,x);
        e1[v].eb(u,-x);
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=n;++i) if(!vs[i]) dfs(i,0);
    for(int i=1;i<=n;++i) for(auto [j,w]:e[i])
        if(bl[i]!=bl[j]) e2[bl[i]].eb(bl[j]);
    for(int i=1;i<=bl[0];++i)
        for(auto j:e2[i]) tg[i]|=tg[j];
    for(int i=1,u;i<=c;++i)
    {
        scanf("%d",&u);
        u=((u%n)+n)%n;
        ++u;
        puts(tg[u]?"Yes":"No");
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 76888kb

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: 79528kb

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: 7ms
memory: 76620kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 9ms
memory: 76132kb

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: 239ms
memory: 98372kb

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
Wrong Answer
time: 289ms
memory: 104708kb

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...

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:

wrong answer 1st words differ - expected: 'Yes', found: 'No'