QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787582 | #9810. Obliviate, Then Reincarnate | ticking_away# | TL | 223ms | 46000kb | C++20 | 4.8kb | 2024-11-27 13:11:28 | 2024-11-27 13:11:30 |
Judging History
answer
#include <bits/stdc++.h>
#define con const
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
#define i128 __int128_t
using u32 = uint32_t;
using u64 = uint64_t;
using f64 = long double;
template<class T>
using lque = priority_queue<T, vector<T>, greater<T>>;
template<class T>
using gque = priority_queue<T>;
template<class T>
void mes(T * arr, int sz=1, int val=0) {
memset(arr, val, sz*sizeof(T));
}
constexpr u32 IBUF_LEN = 1 << 16;
char ibuf[1<<16], *ifr = ibuf, *ied = ibuf;
#define fread() (ied=(ifr=ibuf)+fread(ibuf,1,IBUF_LEN,stdin),ifr==ied) // 单次fread不会等待输入
#define ischar(c) (!isspace(c)&&c!=EOF)
char gc() { return (ifr==ied && fread()) ? EOF : *(ifr++); } // 读取并弹出字符(类似getchar)
char gr() { return (ifr==ied && fread()) ? EOF : *ifr; } // 读取字符
char fit() { while(isspace(gr())) ++ifr; return gr(); } // 将空字符丢弃,并返回第一个非空字符或EOF
#undef fread
template<class T> T &fin(T &v) {
i32 c = v = 0; bool f = fit()=='-'; ifr += f;
while(isdigit(c=gc())) v = v*10 + (c ^ 48);
return f ? (v=-v) : v;
}
template<class T> void fin(T arr[], u32 n) {
for(u32 i=0; i<n; ++i) fin(arr[i]);
}
// 读取非空字符(建议手动gc(),这个只是简写)
template<> char &fin(char &v) { return fit(), v = gc(); }
template<u32 NLEN, u32 ELEN=NLEN*2, class EI=u32>
struct CFS { // 链式前向星
using E = EI; // 此声明用于辅助其他算法的封装
u32 n, hd[NLEN], nx[ELEN], it; EI val[ELEN];
void init(u32 _n) { mes(hd, n=_n, it=-1); } // WARN: INIT!!!
void add(u32 u, con EI &ei) {
nx[++it] = hd[u]; val[it]=ei; hd[u]=it; }
u32 head(con u32 u) con { return hd[u]; }
void next(u32 &e) con { e=nx[e]; }
EI &operator[](con u32 e) { return val[e]; }
};
template<class G, class D>
bool spfa(G &g, u32 s, bool *vis, u32 *cnt, D *dis, D init=0) {
mes(dis, g.n, 0x3f); dis[s]=init;
mes(cnt, g.n); mes(vis, g.n); vis[s]=1;
queue<u32> que; que.push(s);
D ds; typename G::E *ei;
for(u32 u, v; !que.empty();) {
u=que.front(); que.pop(); vis[u]=0;
for(u32 e=g.head(u); ~e; g.next(e))
if(ei=&g[e], (ds=dis[u]+ei->w) < dis[v=ei->v]) {
dis[v] = ds;
cnt[v] = cnt[u] + 1;
if(cnt[v]>g.n) return false;
if(!vis[v]) {
que.push(v), vis[v]=1;
}
}
}
return true;
}
// -------------------
con u32 MX = 5e5 + 7;
con u64 MOD = 998244353;
// con u64 MOD = 1e9+7;
u32 n, m, q;
struct EI{ u32 v; i64 w; };
CFS<MX, MX*4, EI> g, gt;
u32 ite, dfn[MX], low[MX];
// bool vis[MX], ;
u32 ct = 0;
map<u32, u32> mp;
bool vis[MX];
u32 cnt[MX];
i64 dis[MX];
bool check_zero() {
gt.init(ct);
for(auto &[u, mu]:mp) {
for(u32 e=g.head(u), v; ~e; g.next(e)) {
v = g[e].v;
if(mp.count(v)) {
EI ei = g[e];
ei.v = mp[v];
gt.add(mu, ei);
}
}
}
if(!spfa(gt, 0, vis, cnt, dis)) return false;
for(u32 u=0; u<ct; ++u) {
for(u32 e=gt.head(u), v; ~e; gt.next(e)) {
gt[e].w = -gt[e].w;
}
}
return spfa(gt, 0, vis, cnt, dis);
}
bool vs[MX], uz[MX];
vector<u32> stk;
void tarjan(u32 u) {
stk.push_back(u); vs[u] = 1;
dfn[u] = low[u] = ++ite;
for(u32 e=g.head(u), v; ~e; g.next(e)) {
v = g[e].v;
if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
else if(vs[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u]==low[u]) {
mp.clear(); ct = 0;
for(u32 v=-1; v!=u;) {
v = stk.back(); stk.pop_back();
vs[v] = 0; low[v] = dfn[u];
mp[v] = ct++;
}
bool fg = !check_zero();
for(auto [u, _]:mp)
uz[u] = fg;
}
}
void scc() {
for(u32 u=0; u<g.n; ++u)
if(!dfn[u]) tarjan(u);
}
u32 get_pos(i64 x) {
x %= i32(n);
return (x+i32(n)) % n;
}
bool dfs(u32 u) {
if(vs[u]) return uz[u]; vs[u] = 1;
for(u32 e=g.head(u), v; (!uz[u])&&~e; g.next(e))
uz[u] |= dfs(g[e].v);
return uz[u];
}
void solve() {
i64 x = 2;
for(u32 i=0; i<q; ++i) {
bool fg = dfs(get_pos(fin(x)));
if(fg) cout << "Yes\n";
else cout << "No\n";
}
}
void pre() {
fin(n), fin(m), fin(q);
g.init(n);
i64 a, b;
for(u32 i=0; i<m; ++i) {
fin(a), fin(b);
a = get_pos(a);
g.add(a, EI{get_pos(a+b), b});
}
scc();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
u32 _t = 1;
// cin >> _t;
for(;_t--;) {
pre();
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 20072kb
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: 18220kb
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: 17972kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 2ms
memory: 17976kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: 0
Accepted
time: 223ms
memory: 46000kb
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:
ok 500000 tokens
Test #6:
score: -100
Time Limit Exceeded
input:
100848 500000 500000 720352587 361776806 231853504 -933882325 960971230 -83519300 -152772415 -631132247 842871215 -666621297 857194330 -754943024 -698506963 -705416545 -3551931 -927937446 628710320 -942247987 674921043 847145884 -325629529 475694308 -339363446 686789318 236702996 654762989 420412365...