QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865644#9810. Obliviate, Then ReincarnateHanoistWA 101ms38668kbC++143.0kb2025-01-21 20:44:302025-01-21 20:44:30

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 20:44:30]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:38668kb
  • [2025-01-21 20:44:30]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
const int N = 5e5 + 11;
int n,m,q,tt,top,cnt,head[N],stak[N],dfn[N],low[N],col[N],ecnt = -1;
int ecnt1 = -1,head1[N],in1[N],pos[N];
long long val[N];
bool vis[N],flag[N];
struct yjx{
    int nxt,to;
    long long c;
}e[N],e1[N];
inline void save(int x,int y,int w){
    e[++ecnt] = (yjx){head[x],y,w};
    head[x] = ecnt;
}
inline void save1(int x,int y,int w){
    e1[++ecnt1] = (yjx){head1[x],y,w};
    head1[x] = ecnt1;
    ++in1[y];
}
void tarjan(int now){
    int i,temp;
    dfn[now] = low[now] = ++tt;
    stak[++top] = now;
    for(i = head[now];~i;i = e[i].nxt){
        temp = e[i].to;
        if(!dfn[temp]){
            tarjan(temp);
            low[now] = min(low[now],low[temp]);
        }
        else if(!col[temp]) low[now] = min(low[now],low[temp]);
    }
    if(dfn[now] == low[now]){
        col[now] = ++cnt;
        pos[cnt] = now;
        while(now != stak[top]){
            col[stak[top--]] = cnt;
        }
        --top;
    }
}
void dfs(int now){
    int i,temp;
    vis[now] = 1;
    for(i = head[now];~i;i = e[i].nxt){
        temp = e[i].to;
        if(col[temp] != col[now]) continue;
        if(vis[temp]){
            if(val[temp] != val[now] + e[i].c) flag[col[now]] = 1;
            continue;
        }
        val[temp] = val[now] + e[i].c;
        dfs(temp);
    }
}
void solve(){
    int i;
    for(i = 1;i <= cnt;i++){
        val[pos[i]] = 0;
        dfs(pos[i]);
    }
}
void rebuild(){
    int i,j,k;
    for(i = 0;i < n;i++){
        for(j = head[i];~j;j = e[j].nxt){
            k = e[j].to;
            if(col[i] != col[k]) save1(col[k],col[i],0);
        }
    }
}
void topo(){
    queue<int> Q;
    int i,now,temp;
    for(i = 1;i <= cnt;i++){
        if(!in1[i]) Q.push(i);
    }
    while(!Q.empty()){
        now = Q.front();
        Q.pop();
        for(i = head1[now];~i;i = e1[i].nxt){
            temp = e1[i].to;
            if(flag[now]) flag[temp] = 1;
            --in1[temp];
            if(!in1[temp]) Q.push(in1[temp]);
        }
    }
}
int main(){
    int t,i,j,x,y;
    n = read(),m = read(),q = read();
    memset(head1,-1,sizeof(head1));
    memset(head,-1,sizeof(head));
    for(i = 1;i <= m;i++){
        x = read(),y = read();
        x = (x % n + n) % n;
        save(x,x + (y % n + n) % n,y);
    }
    for(i = 0;i < n;i++){
        if(!dfn[i]) tarjan(i);
    }
    solve();
    rebuild();
    topo();
    for(i = 1;i <= q;i++){
        x = read();
        if(flag[col[(x + n % n) % n]]) puts("Yes");
        else puts("No");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 23724kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 21960kb

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

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

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'