QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801023#9810. Obliviate, Then Reincarnateucup-team135#Compile Error//Python33.6kb2024-12-06 17:43:582024-12-06 17:44:05

Judging History

This is the latest submission verdict.

  • [2024-12-06 17:44:05]
  • Judged
  • [2024-12-06 17:43:58]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)

vector<int> find_scc(vector<vector<int>> g, int &color) {
  vector<vector<int>> r(g.size());
  for (int i = 0; i < g.size(); ++i) {
    for (int j : g[i]) r[j].push_back(i);
  }
  vector<int> used(g.size()), tout(g.size());
  int time = 0;
  auto dfs = [&](auto dfs, int cur) -> void {
    if (used[cur]) return;
    used[cur] = 1;
    for (int nxt : g[cur]) {
      dfs(dfs, nxt);
    }
    tout[cur] = time++;
  };
  for (int i = 0; i < g.size(); ++i) if (!used[i]) dfs(dfs, i);
  vector<int> ind(g.size());
  iota(ind.begin(), ind.end(), 0);
  sort(all(ind), [&](int i, int j){return tout[i] > tout[j];});
  vector<int> scc(g.size(), -1);
  auto go = [&](auto go, int cur, int color) -> void {
    if (scc[cur] != -1) return;
    scc[cur] = color;
    for (int nxt : r[cur]) {
      go(go, nxt, color);
    }
  };
  for (int i : ind) {
    if (scc[i] == -1) go(go, i, color++);
  }
  return scc;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;

    vector <array <int, 3> > e;
    vector <vector <int> > og(n), ng;
    vector <vector <pair <int, int> > >gg(n);
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        a = (a % n + n) % n;

        int to = ((a + b) % n + n) % n;

        og[a].app(to);
        gg[a].app({to, b});
        e.app({a, to, b});
    }

    int color = 0;
    auto scc = find_scc(og, color);

    ng.resize(color);
    for (auto [u, v, d] : e) {
        u = scc[u]; v = scc[v];
        ng[u].app(v);
    }

    vector <int> start(color);
    for (int i = 0; i < n; ++i) {
        start[scc[i]]=i;
    }

    vector <int> p(n), used(n);
    function <void(int)> dfs = [&] (int u) {
        used[u] = 1;
        for (auto [v, d] : gg[u]) {
            if (scc[u] != scc[v]) {
                continue;
            }
            if (!used[v]) {
                p[v] = p[u] + d;
                dfs(v);
            }
        }
    };

    debug("here");
    for (int c = 0; c < color; ++c) {
        dfs(start[c]);
    }
    debug("dfs");

    vector <int> mon(color);
    for (auto [u, v, d] : e) {
        if (scc[u] == scc[v]) {
            if (p[u] + d != p[v]) {
                mon[scc[u]] = 1;
            }
        }
    }

    function <void(int)> go = [&] (int u) {
        used[u] = 1;
        for (int v : ng[u]) {
            if (!used[v]) {
                go(v);
                mon[u] |= mon[v];
            }
        }
    };

    used.assign(color, 0);
    for (int i = 0; i < color; ++i) {
        if (!used[i]) {
            go(i);
        }
    }

    while (q--) {
        int a; cin >> a;
        a = (a % n + n) % n;
        if (mon[scc[a]]) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }

    return 0;
}

Details

  File "answer.code", line 6
    int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
                                                                                                     ^
SyntaxError: invalid decimal literal