QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794829#9810. Obliviate, Then Reincarnateucup-team5234#WA 348ms60616kbC++205.2kb2024-11-30 16:17:142024-11-30 16:17:14

Judging History

This is the latest submission verdict.

  • [2024-11-30 16:17:14]
  • Judged
  • Verdict: WA
  • Time: 348ms
  • Memory: 60616kb
  • [2024-11-30 16:17:14]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T> using VVVV = VV<VV<T>>;
#define rep(i,n) for(ll i=0ll;i<n;i++)
#define REP(i,a,n) for(ll i=a;i<n;i++)
const long long INF = (1LL << 60);
const long long mod99 = 998244353;
const long long mod107 = 1000000007;
const long long mod = mod99;
#define eb emplace_back
#define be(v) (v).begin(),(v).end()
#define all(i,v) for(auto& i : v)
#define UQ(v) sort(be(v)), v.erase(unique(be(v)), v.end())
#define LB(x,v) (lower_bound(be(v),(x))-(v).begin())
#define UB(x,v) (upper_bound(be(v),(x))-(v).begin())
#define dout()  cout << fixed << setprecision(20)
#define randinit() srand((unsigned)time(NULL))

template<class T, class U> bool chmin(T& t, const U& u) { if (t > u){ t = u; return 1;} return 0; }
template<class T, class U> bool chmax(T& t, const U& u) { if (t < u){ t = u; return 1;} return 0; }



struct scc_graph{
  vector<vector<ll>> G, G_inv;
  vector<ll> res, vv;
  vector<bool> used;
  ll size, idx;
  ll f;
  
  scc_graph(ll N) : G(N), G_inv(N), used(N), res(N), size() {
    size = N;
  }
  
  void add_edge(ll u, ll v){
    G[u].push_back(v);
    G_inv[v].push_back(u);
  }
  
  void dfs(ll nd){
    used[nd] = 1;
    for(auto nx : G[nd]) if(!used[nx]) dfs(nx);
    res[idx] = nd;
    idx ++;
  }
  
  void ddfs(ll nd, ll par){
    vv.push_back(nd);
    used[nd] = 1;
    for(auto nx : G_inv[nd]){
      if(nx == par) f = 1;
      if(!used[nx]) ddfs(nx, par);
    }
  }
  
  vector<vector<ll>> scc(){
    vector<vector<ll>> ans;
    idx = 0;
    used.assign(size, 0);
    rep(i, size) if(!used[i]) dfs(i);
    
    idx = 0;
    used.assign(size, 0);
    for(ll i = size-1; i >= 0; i --){
      if(!used[res[i]]){
        f = 0;
        vv.resize(0);
        ddfs(res[i], res[i]);
        if(f) ans.push_back(vv);
      }
    }
    return ans;
  }
};

template <typename T, T (*OP)(T, T), T (*INV)(T), T (*E)()>
struct PotentialUnionFind{
    vector<long long> par; 
    long long gn;
    vector<T> weight;
    PotentialUnionFind(long long N) : par(N, -1), gn(N), weight(N, E()){ }

    long long root(long long x) { 
        if (par[x] < 0) return x;
        long long r = root(par[x]);
        weight[x] = OP(weight[x], weight[par[x]]);
        return par[x] = r;
    }

    long long size(long long x) {
        return -par[root(x)];
    }
    
    T _weight(long long x){
        root(x);
		return weight[x];
    }
  
    bool merge(long long x, long long y, T w) { 
        long long rx = root(x), ry = root(y); 
        w = OP(w, _weight(y));
        w = OP(w, INV(_weight(x)));
        if (rx == ry) return 0; 
        gn --;
        if (par[rx] < par[ry]){
            swap(rx, ry);
            w = INV(w);
        }
        par[ry] += par[rx];
        par[rx] = ry; 
        weight[rx] = w;
        return 1;
    }
    

	T diff(long long x, long long y) {
		return OP(_weight(y), INV(_weight(x)));
	}
	
    bool same(long long x, long long y) {
        return root(x) == root(y);
    }
};



template<typename S>
S e(){return 0;}
template<typename S>
S op(S L, S R){return L+R;}
template<typename S>
S inv(S L){return -L;}




void solve(){
    ll n,m,q;
    cin >> n >> m >> q;
    V<ll> x(m), y(m);
    scc_graph g(n);
    rep(i, m){
        cin >> x[i] >> y[i];
        x[i] = ((x[i]%n)+n)%n;
        ll a = (x[i] + y[i]) % n;
        if(a < 0) a += n;
        if(x[i]!=a) g.add_edge(x[i], a);
    }
    
    auto scc = g.scc();
    V<ll> value(n, INF);
    queue<ll> que;
    for(auto v:scc){
        ll nd = v[0];
        value[nd] = 0;
        que.push(nd);
    }
    VV<pair<ll,ll>> G(n), Gi(n);
    rep(i, m) if(y[i]) {
        ll a = x[i];
        ll b = (x[i] + y[i])%n;
        if(b<0) b+=n;
        ll c = y[i];
        G[a].eb(b, c);
        Gi[b].eb(a, -c);
    }
    
    // cout << "OK" << endl;
    while(!que.empty()){
        ll nd = que.front();
        que.pop();
        for(auto [nx, c]:Gi[nd]) if(value[nx] == INF){
            value[nx] = value[nd] + c;
            que.push(nx);
        }
    }
    // cout << "OK" << endl;
    V<ll> ok(n, 0);
    rep(nd, n) if(value[nd] != INF) {
        for(auto [nx, c]:Gi[nd]) if(value[nd]+c != value[nx] and !ok[nx]){
            que.push(nx);
            ok[nx] = 1;
        }
    }
    rep(nd, n) if(!ok[nd]){
        for(auto [nx, c]:Gi[nd]) if(nx == nd and c != 0){
            que.push(nd);
            ok[nd] = 1;
        }
    }
    // cout << "OK" << endl;
    while(!que.empty()){
        ll nd = que.front();
        que.pop();
        for(auto [nx, _]:Gi[nd]) if(!ok[nx]){
            ok[nx] = 1;
            que.push(nx);
        }
    }

    rep(i, q){
        ll t;
        cin >> t;
        t = ((t%n)+n)%n;
        if(ok[t]) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
}





int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t=1;
    // cin >> t;
    rep(i,t) solve();
}

详细

Test #1:

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

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

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: 0ms
memory: 3500kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

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: 348ms
memory: 60616kb

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 70268th words differ - expected: 'No', found: 'Yes'