QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#819876#9810. Obliviate, Then ReincarnateMagical_KingdomWA 5ms44160kbC++203.7kb2024-12-18 17:56:002024-12-18 17:56:02

Judging History

This is the latest submission verdict.

  • [2024-12-18 17:56:02]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 44160kb
  • [2024-12-18 17:56:00]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int maxn = 5e5 + 7;
ll n, m, q;
struct Edge {
    ll v, w;
    Edge(ll _v = 0, ll _w = 0)
        : v(_v), w(_w) {}
};
vector<Edge> to[maxn];

ll dfn[maxn], low[maxn], cnt, tot;
ll vis[maxn], belong[maxn], inde, belong_num[maxn], num_inde;
ll indegree[maxn], outdegree[maxn];
stack<ll> st;
void tarjin(ll x) {
    dfn[x] = low[x] = ++tot;
    vis[x] = 1;
    st.push(x);
    for (auto [v, w] : to[x]) {
        if (!dfn[v]) {
            tarjin(v);
            low[x] = min(low[x], low[v]);
        } else if (vis[v] == 1) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (dfn[x] == low[x]) {
        ll v;
        inde = inde + 1;
        do {
            v = st.top();
            st.pop();
            belong[v] = inde;
            belong_num[inde]++;
            vis[v] = 0;
        } while (v != x);
    }
}

ll stk[maxn], top, loc[maxn];

ll sum_min[maxn], sum_max[maxn];
bool in_stk[maxn];
set<int> visited;

bool can[maxn];
void dfs(int u) {
    stk[++top] = u;
    loc[u] = top;

    map<ll, pll> mp;
    for (auto [v, w] : to[u]) {
        if (belong[v] != belong[u]) {
            continue;
        }
        if (mp.find(v) == mp.end()) {
            mp[v].first = mp[v].second = w;
        } else {
            mp[v].first = min(w, mp[v].first);
            mp[v].second = max(w, mp[v].second);
        }
    }

    for (auto [v, w] : mp) {
        ll wmin = w.first, wmax = w.second;
        if (in_stk[v] == true) {
            if (sum_max[top] - sum_max[loc[v]] + wmax == 0 &&
                sum_min[top] - sum_min[loc[v]] + wmin == 0) {
                continue;
            } else {
                can[belong[u]] = true;
                loc[u] = 0;
                stk[top--] = 0;
                return;
            }
        }
        if (visited.find(v) != visited.end()) {
            continue;
        }
        visited.insert(v);
        in_stk[v] = true;
        sum_min[top + 1] = sum_min[top] + wmin;
        sum_max[top + 1] = sum_max[top] + wmax;
        dfs(v);
        sum_min[top + 1] = 0;
        sum_max[top + 1] = 0;
        in_stk[v] = false;
        if (can[belong[u]] == true) {
            loc[u] = 0;
            stk[top--] = 0;
            return;
        }
    }
    loc[u] = 0;
    stk[top--] = 0;
    return;
}

set<int> nto[maxn];

void dfs2(int u) {
    can[u] = true;
    for (auto v : nto[u]) {
        if (!can[v]) {
            dfs2(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        ll u, w;
        cin >> u >> w;
        ll v = u + w;
        u = (u % n + n) % n;
        v = (v % n + n) % n;
        to[u].push_back(Edge(v, w));
    }
    for (int i = 0; i < n; i++) {
        if (!dfn[i]) {
            tarjin(i);
        }
    }

    for (int i = 1; i <= inde; i++) {
        visited.clear();
        top = 0;
        sum_min[i] = sum_max[i] = 0;
        in_stk[i] = 1;
        dfs(i);
        in_stk[i] = 0;
    }

    for (int u = 0; u < n; u++) {
        for (auto e : to[u]) {
            int v = e.v;
            if (belong[u] != belong[v]) {
                nto[belong[v]].insert(belong[u]);
            }
        }
    }

    for (int i = 1; i <= inde; i++) {
        if (can[i] == true) {
            dfs2(i);
        }
    }

    while (q--) {
        ll x;
        cin >> x;
        x = (x % n + n) % n;
        if (can[belong[x]]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 42920kb

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

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

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

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