QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#792695#9810. Obliviate, Then ReincarnateCORRECTWA 0ms3820kbC++204.1kb2024-11-29 13:04:412024-11-29 13:04:43

Judging History

This is the latest submission verdict.

  • [2024-11-29 13:04:43]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3820kb
  • [2024-11-29 13:04:41]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL nonum = (LL)1e16;

vector<int> sz;
vector<vector<int> > scc;

void tarjan(int x, int dfncnt, vector<vector<array<LL, 2> > > &bian, vector<int> &dfn, vector<int> &low, stack<int> &st, vector<int> inst) {
    dfncnt ++;  dfn[x] = dfncnt;  low[x] = dfncnt;
    st.push(x);  inst[x] = 1;
    for (auto &[to, val] : bian[x]) {
        if (!dfn[to] ) {
            tarjan(to, dfncnt, bian, dfn, low, st, inst);
            low[x] = min(low[x], low[to]);
        } else if (inst[to] ) {
            low[x] = min(low[x], low[to]);
        }
    }
    if (dfn[x] == low[x] ) {
        scc.push_back(vector<int>());
        while (inst[x] ) {
            scc[scc.size()-1].push_back(st.top());
            inst[st.top()] = 0;
            st.pop();
        }
    }
}
void tarjanfun(int n, vector<vector<array<LL, 2> > > &bian) {
    sz = vector<int> (n+10, 0);
    vector<int> dfn(n+10, 0), low(dfn), inst(dfn);
    stack<int> st;
    tarjan(1, 0, bian, dfn, low, st, inst);
}

void work() {
    LL n, m, q;
    cin >> n >> m >> q;
    vector<vector<array<LL, 2> > > bian(n+10, vector<array<LL, 2> > ());
    vector<vector<int> > fubian(n+10, vector<int> ());
    vector<int> ans(n+10, 0);
    for (int i=1; i<=m; i++) {
        int u, v, w;  cin >> u >> w;
        u = (u % n + n) % n;
        v = (w % n + n) % n;
        v = (u + v) % n;
        // cout << u << ' ' << v << ' ' << w << '\n';
        if (u == v) {
            if (w == 0)  continue;
            ans[u] = 1;  continue;
        }
        bian[u].push_back({v, w});
        fubian[v].push_back(u);
    }
    for (int i=0; i<n; i++) {
        if (ans[i] ) {
            queue<int> ansqu;  ansqu.push(i);
            ans[i] = 1;
            while (!ansqu.empty() ) {
                int x = ansqu.front();  ansqu.pop();
                for (auto &u : fubian[x]) {
                    if (ans[u] == 0)  ansqu.push(u);
                    ans[u] = 1;
                }
            }
        }
    }
    tarjanfun(n, bian);
    for (int sccid = 0; sccid < scc.size(); sccid ++) {
        auto &p = scc[sccid];
        if (p.size() == 1 || ans[p[0]] )  continue;
        map<int, int> mp;
        int siz = 0;
        for (auto &x : p) {
            siz ++;  mp[x] = siz;
        }
        vector<vector<array<LL, 2> > > fbian(siz + 10, vector<array<LL, 2> > ());
        vector<int> rudu(siz+10, 0);
        for (auto &x : p) {
            int fx = mp[x];
            for (auto &[to, val] : bian[x]) {
                if (mp.find(to) == mp.end() )  continue;
                int fto = mp[to];
                fbian[fx].push_back({fto, val});
                rudu[fto] ++;
            }
        }
        vector<LL> num(siz+10, nonum);
        num[1] = 0;
        queue<int> qu;  qu.push(1);
        bool bo = false;
        while (!qu.empty()) {
            int x = qu.front();  qu.pop();
            for (auto &[to, val] : fbian[x]) {
                if (num[to] != nonum && num[x] + val != num[to]) {
                    bo = true;  break;
                }
                rudu[to] --;
                if (rudu[to] == 0) {
                    qu.push(to);
                }
            }
            if (bo )  break;
        }
        if (bo ) {
            queue<int> ansqu;  ansqu.push(p[0]);
            ans[p[0]] = 1;
            while (!ansqu.empty() ) {
                int x = ansqu.front();  ansqu.pop();
                for (auto &u : fubian[x]) {
                    if (ans[u] == 0)  ansqu.push(u);
                    ans[u] = 1;
                }
            }
        }
    }
    while (q --) {
        int x;  cin >> x;
        x = (x % n + n) % n;
        if (ans[x] ) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}
int main()
{
    #ifdef QHK
    freopen("qi.in","r",stdin);
    freopen("qi.out","w",stdout);
    #endif
    ios::sync_with_stdio(false); cin.tie(0); 
    int T=1;
    // cin >> T;
    while(T--) {
        work();
    }

   return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3820kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'