QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794173#9810. Obliviate, Then ReincarnateMYdinosaurWA 4ms40424kbC++143.0kb2024-11-30 12:33:502024-11-30 12:33:51

Judging History

This is the latest submission verdict.

  • [2024-11-30 12:33:51]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 40424kb
  • [2024-11-30 12:33:50]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, ll> pa;
const int N = 5e5 + 10;
int spec = 0;
int abc[N], abcd[N], a[N];
int vis[N], dfn[N], low[N];
int cnt = 0, tot = 0;
vector <int> sdf[N];
vector <pa> v[N];
int bj[N];
int na[N];
int f[N];
stack <int> q;


inline void read(ll &x)
{
    ll w = 1; x = 0; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + (ch ^ 48); ch = getchar();}
    x = x * w;
}

void dg(int x)
{
    vis[x] = 1;
    cnt ++;
    dfn[x] = low[x] = cnt;
    q.push(x);
    for (int i = 0; i < v[x].size(); i++)
    {
        int y = v[x][i].first;
        if (abc[y] == 1) continue;
        if (dfn[y] == 0)
        {
            dg(y);
            low[x] = min(low[x], low[y]);
        }
        else if (!bj[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        tot ++;
        a[tot] = x;
        while (!q.empty())
        {
            int t = q.top();
            q.pop();
            bj[t] = tot;
            if (t == x) break;
        }
    }
}

void dfs(int x)
{
    for (int i = 0; i < sdf[x].size(); i++)
    {
        int y = sdf[x][i];
        if (abc[y] == 1) continue;
        abc[y] = 1;
        dfs(y);
    }
}

int work(int fa, int da)
{
    int ind = 0;
    queue <int> q;
    f[fa] = 0;
    q.push(fa);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v[x].size(); i++)
        {
            int y = v[x][i].first;
            int z = v[x][i].second;
            if (bj[y] != da) continue;
            if (f[y] == -1) 
            {
                q.push(y);
            }
            else if (f[y] != f[x] + z) return 1;
        }
    }
    return 0;
}

int main()
{
    ll n, m, qe;
    read(n); read(m); read(qe);
    for (int i = 1; i <= m; i++)
    {
        ll x, y;
        read(x); read(y);
        if (y == 0) continue;
        ll t = (x + y) % n;
        x = x % n;
        x = (x + n) % n;
        t = (t + n) % n;
        // cout << x << " " << t << endl;
        sdf[t].push_back(x);
        if (x == t)
        {
            spec++;
            abc[x] = 1;
            abcd[spec] = x;
        }
        else
        {
            v[x].push_back({t, y});
        }
    }
    for (int i = 1; i <= spec; i++)
    {
        // cout << i << " " << sdf[i].size() << endl;
        dfs(abcd[i]);
    }
    for (int i = 0; i < n; i++)
    {
        f[i] = -1;

        if (abc[i] == 1) continue;
        if (!vis[i]) dg(i);
    }
    for (int i = 1; i <= tot; i++)
    {
        int x = a[i];
        na[i] = work(x, i);
    }
    for (int i = 1; i <= qe; i++)
    {
        ll x;
        read(x);
        x = x % n;
        if (abc[x] == 1 || na[bj[x]] == 1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


詳細信息

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 34348kb

input:

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

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'