QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794737#9810. Obliviate, Then Reincarnateucup-team5234#WA 1ms3892kbC++205.0kb2024-11-30 15:42:412024-11-30 15:42:42

Judging History

This is the latest submission verdict.

  • [2024-11-30 15:42:42]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3892kb
  • [2024-11-30 15:42:41]
  • 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;
    VV<ll> G(n);
    scc_graph g(n);
    V<map<ll,ll>> weight1(n), weight2(n);
    rep(i, m){
        ll x,y;
        cin >> x >> y;
        if(y){
            ll a = (x+y)%n;
            x = ((x%n)+n)%n;
            G[a].eb(x);
            g.add_edge(x, a);
            if(x > a){
                swap(x, a);
                y = -y;
            }
            if(!weight1[x].count(a)){
                weight1[x][a] = y;
                weight2[x][a] = y;
            }else{
                chmax(weight1[x][a], y);
                chmin(weight2[x][a], y);
            }
        }
    }
    
    PotentialUnionFind<ll, op, inv, e> uf1(n), uf2(n);
    rep(i, n){
        for(auto[a,b]:weight1[i]) uf1.merge(i, a, b);
        for(auto[a,b]:weight2[i]) uf2.merge(i, a, b);
    }

    auto scc = g.scc();
    V<ll> ok(n, 0);
    queue<ll> que;
    for(auto v:scc){
        ll a = v[0], b = v[1];
        ll c1 = uf1.diff(a, b), c2 = uf2.diff(a, b);
        if(c1 != b-a || c2 != b-a){
            for(auto x:v){
                ok[x] = 1;
                que.push(x);
            }
        }
    }
    while(!que.empty()){
        ll nd = que.front();
        que.pop();
        for(auto nx:G[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: 1ms
memory: 3692kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

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