QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#794829 | #9810. Obliviate, Then Reincarnate | ucup-team5234# | WA | 348ms | 60616kb | C++20 | 5.2kb | 2024-11-30 16:17:14 | 2024-11-30 16:17:14 |
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;
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'