QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782658#9810. Obliviate, Then ReincarnateAndyqian7WA 283ms33792kbC++202.4kb2024-11-25 20:53:472024-11-25 20:54:15

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 20:54:15]
  • Judged
  • Verdict: WA
  • Time: 283ms
  • Memory: 33792kb
  • [2024-11-25 20:53:47]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i, s, e) for (int i = s; i <= e; i++)
using namespace std;
const int N = 1e6 + 10;
vector<int> e[N], sta, com[N], ie[N];
int n, m, q, dfn[N], low[N], f[N], vis[N], dfsOrder, sccnum, ok[N], val[N];
void tarjan(int u)
{
    dfn[u] = low[u] = ++dfsOrder;
    sta.push_back(u);
    vis[u] = 1;
    for (auto &v : e[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] != low[u])
        return;
    ++sccnum;
    vector<int>::iterator it = (--sta.end());
    for (f[u] = sccnum, vis[u] = 0; *it != u; --it)
        f[*it] = sccnum, vis[*it] = 0;
    sta.erase(it, sta.end());
}
struct edge
{
    int to, val;
};
vector<edge> g[N];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    rep(i, 1, m)
    {
        int a, b;
        cin >> a >> b;
        int c = b;
        a = (a % n + n) % n, b = (b % n + n) % n;
        e[a + 1].push_back((a + b) % n + 1);
        ie[(a + b) % n + 1].push_back(a + 1);
        g[a + 1].push_back({(a + b) % n + 1, c});
    }
    rep(i, 1, n) if (!dfn[i]) tarjan(i);
    rep(i, 1, n)
    {
        com[f[i]].push_back(i);
    }
    rep(i, 1, n)
        vis[i] = 0;
    rep(i, 1, sccnum)
    {
        queue<int> Q;
        for (int j : com[i])
        {
            Q.push(j);
        }
        while (Q.size())
        {
            int t = Q.front();
            Q.pop();
            vis[t] = 1;
            for (auto [son, dis] : g[t])
            {
                if (f[son] != f[t])
                    continue;
                if (vis[son])
                {
                    if (val[son] != val[t] + dis)
                        ok[i] = 1;
                }
                else
                {
                    val[son] = val[t] + dis;
                    Q.push(son);
                }
            }
        }
        if (ok[i])
            for (int j : com[i])
            {
                for (int k : ie[j])
                {
                    ok[f[k]] = 1;
                }
            }
    }
    while (q--)
    {
        int x;
        cin >> x;
        x = (x % n + n) % n;
        cout << (ok[x + 1] ? "Yes" : "No") << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9724kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9988kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Wrong Answer
time: 283ms
memory: 33792kb

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:

wrong answer 55056th words differ - expected: 'No', found: 'Yes'