QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#794737 | #9810. Obliviate, Then Reincarnate | ucup-team5234# | WA | 1ms | 3892kb | C++20 | 5.0kb | 2024-11-30 15:42:41 | 2024-11-30 15:42:42 |
Judging History
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'