QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810953#9810. Obliviate, Then ReincarnateFalse0099RE 0ms20524kbC++203.2kb2024-12-12 13:54:352024-12-12 13:54:37

Judging History

This is the latest submission verdict.

  • [2024-12-12 13:54:37]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 20524kb
  • [2024-12-12 13:54:35]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 10, M = 1e6 + 10;

int n, m, mod;
int h[N], e[M << 1], ne[M << 1], idx, val[N]; // 原图参数
/*tarjan中间量*/
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
/*tarjan中间量*/
int id[N], scc_size[N];          // 新旧关系
int scc_cnt;                     // 新图的n
int hs[N], sum[N], dp[N], in[N]; // 新图的参数
int ans;

void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sum[scc_cnt] += val[y]; // 处理我们的合并点
            scc_size[scc_cnt]++;
        } while (y != u);
    }
}

void topsort()
{
    queue<int> q;
    for (int i = 1; i <= scc_cnt; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        if (scc_size[now] > 1)
        {
            dp[now] = 1;
        }
        for (int i = hs[now]; i != -1; i = ne[i])
        {
            int v = e[i];
            in[v]--;
            dp[v] = (dp[v] | dp[now]);
            if (in[v] == 0)
            {
                q.push(v);
            }
        }
    }
}

signed main()
{
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    int q;
    cin >> n >> m >> q;
    // for (int i = 1; i <= n; i++)
    // {
    //     cin >> val[i];
    // }
    set<array<int, 2>> edges;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a = (a + n) % n;
        if (b == 0)
        {
            continue;
        }
        else
        {
            edges.insert({a, (a + b) % n});
            //cerr << a << " " << (a + b) % n << endl;
            add(h, a, (a + b) % n);
        }
        add(h, a, b);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            tarjan(i);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                add(hs, b, a);
                in[a]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (edges.count({i, i}))
        {
            dp[id[i]] = 1;
        }
    }
    topsort();
    while (q--)
    {
        int u;
        cin >> u;
        if (dp[id[u]] == true)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    // cout << ans << endl;
}

詳細信息

Test #1:

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

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Runtime Error

input:

1 1 1
0 1000000000
-1000000000

output:


result: