QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791225#9810. Obliviate, Then Reincarnateguodong#WA 0ms43404kbC++173.0kb2024-11-28 17:32:322024-11-28 17:32:32

Judging History

This is the latest submission verdict.

  • [2024-11-28 17:32:32]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 43404kb
  • [2024-11-28 17:32:32]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long 
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define clr(x, y) memset(x, y, sizeof(x))

using namespace std;

const int MAXN = 5e5 + 5;
const int INF = 1e15;
int cnt2, tot, top;
queue<int> que;
int dfn[MAXN], low[MAXN], sta[MAXN], insta[MAXN], dis[MAXN], col[MAXN], flag[MAXN];
int flag2[MAXN], ans[MAXN], c[MAXN];

struct graph{
    int cnt;
    int head[MAXN], nxt[MAXN], to[MAXN], value[MAXN];

    void init(){
        cnt = 0;
        clr(head, -1);
    }

    void addedge(int u, int v, int w){
        nxt[cnt] = head[u];
        head[u] = cnt;
        to[cnt] = v;
        value[cnt] = w;
        cnt++;
    }

} G1, G2;

void dfs(int u, int id){
    for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
        int v = G1.to[e];
        if(col[u] != col[v]) continue;
        if(dis[v] != INF){
            if(dis[v] != dis[u] + G1.value[e]) flag[id] = 1;
            continue;
        }
        dis[v] = dis[u] + G1.value[e];
        dfs(v, id);
    }
}

void tarjan(int u){
    dfn[u] = low[u] = ++cnt2;
    sta[++top] = u;
    insta[u] = 1;
    for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
        int v = G1.to[e];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(insta[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        tot++;
        do{
            col[sta[top]] = tot;
            insta[sta[top]] = 0;
        }while(sta[top--] != u);
    }
}

signed main(){
    int n, m, q;
    scanf("%lld%lld%lld", &n, &m, &q);
    G1.init(); G2.init();
    rep(i, 1, m){
        int a, b;
        scanf("%lld%lld", &a, &b);
        int u = (a % n + n - 1) % n + 1, v = ((a + b) % n + n - 1) % n + 1;
        if(u != v) G1.addedge(u, v, b);
        else{
            if(b) flag2[u] = 1;
        }
    }
    rep(i, 1, n){
        if(!dfn[i]) tarjan(i);
    }
    clr(flag, -1);
    rep(i, 1, n) dis[i] = INF;
    rep(i, 1, n){
        if(flag[col[i]] != -1) continue;
        flag[col[i]] = 0;
        dis[i] = 0;
        dfs(i, col[i]);
    }
    // puts("xxxxxxxxxx");
    rep(i, 1, n) if(flag2[i]) flag[col[i]] = 1;
    rep(u, 1, n){
        for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
            int v = G1.to[e];
            if(col[u] == col[v]) continue;
            G2.addedge(col[v], col[u], 0);
            c[col[u]]++;
        }
    }
    // puts("xxxxxx");
    rep(i, 1, tot){
        if(!c[i]) que.push(i);
        ans[i] = flag[i];
    }
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int e = G2.head[u]; e != -1; e = G2.nxt[e]){
            int v = G2.to[e];
            ans[v] |= ans[u];
            c[v]--;
            if(!c[v]) que.push(v);
        }
    }
    // puts("xxxxxxxxxx");
    while(q--){
        int x;
        scanf("%lld", &x);
        if(ans[col[x]]) puts("YES");
        else puts("NO");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 43404kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

YES
YES
NO

result:

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