QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#787578#9810. Obliviate, Then Reincarnateticking_away#TL 272ms44064kbC++204.8kb2024-11-27 13:07:372024-11-27 13:07:42

Judging History

This is the latest submission verdict.

  • [2024-11-27 13:07:42]
  • Judged
  • Verdict: TL
  • Time: 272ms
  • Memory: 44064kb
  • [2024-11-27 13:07:37]
  • Submitted

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])
                if(dis[v] = ds, !vis[v]) {
                    cnt[v] = cnt[u] + 1;
                    if(cnt[v]>g.n) return false;
                    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: 22064kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

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: 272ms
memory: 44064kb

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...

output:


result: