QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811017#9810. Obliviate, Then ReincarnateFalse0099WA 607ms81236kbC++203.2kb2024-12-12 14:44:542024-12-12 14:45:01

Judging History

This is the latest submission verdict.

  • [2024-12-12 14:45:01]
  • Judged
  • Verdict: WA
  • Time: 607ms
  • Memory: 81236kb
  • [2024-12-12 14:44:54]
  • Submitted

answer

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

const int N = 2e6 + 10, M = 2e6 + 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;
bool vis[N];
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]++;
            // dp[scc_cnt] |= vis[y];
        } while (y != u);
    }
}

void topsort()
{
    queue<int> q;
    for (int i = 1; i <= scc_cnt; i++)
    {
        if (in[i] == 0)
        {
            //cerr << i << endl;
            q.push(i);
            if (sum[i] != 0)
            {
                dp[i] = 1;
            }
        }
    }
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        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;
    //    set<array<int, 2>> edges;
    vector<array<int, 3>> edge;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a %= n;
        // b %= n;
        a = (a + n) % n;

        edge.push_back({a, (a + b + n) % n, b});
        add(h, a, (a + b + n) % n);
    }

    for (int i = 0; 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 (auto [u, v, w] : edge)
    {
        if (id[u] == id[v])
        {
            //cerr << u << " " << v << " " << w << endl;
            sum[id[u]] += w;
        }
    }
    topsort();
    // cerr << "q" << endl;
    while (q--)
    {
        int u;
        cin >> u;
        u %= n;
        u = (u + n) % n;
        //cerr << u << " " << id[u] << endl;
        if (dp[id[u]] == true)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    // cout << ans << endl;
}

详细

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 6ms
memory: 46852kb

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

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

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'