QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789270#9802. Light Up the Griducup-team5071#WA 3ms7720kbC++203.4kb2024-11-27 19:43:082024-11-27 19:43:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 19:43:08]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7720kb
  • [2024-11-27 19:43:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
stack<int> s;
vector<pair<int, ll>> ve[maxn];
vector<int> ve2[maxn];
int col[maxn], num, dfn[maxn], low[maxn], dfstime;
vector<int> color_have[maxn];
int ok[maxn];
void tarjan(int u)
{
    // cout << "tarjan u=" << u << endl;
    s.push(u);
    dfn[u] = low[u] = ++dfstime;
    for (auto [v, len] : ve[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!col[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        col[u] = ++num;
        while (s.top() != u)
        {
            col[s.top()] = num;
            s.pop();
        }
        s.pop();
    }
}
ll dis[maxn];
int vis[maxn];
int check_color(int c)
{
    // cout << "c=" << c << endl;
    // for (auto it : color_have[c])
    //     cout << it << " ";
    // cout << endl;
    queue<pair<int, ll>> qu;
    qu.push({color_have[c].front(), 0});
    while (!qu.empty())
    {
        auto [x, len] = qu.front();
        qu.pop();
        if (vis[x])
        {
            if (len != dis[x])
                return 1;
            continue;
        }
        vis[x] = 1;
        dis[x] = len;
        auto it = lower_bound(ve[x].begin(), ve[x].end(), make_pair(c, (ll)-2e9), [&](pair<int, ll> a, pair<int, ll> b)
                              { return col[a.first] < col[b.first]; });
        while (it != ve[x].end() && col[it->first] == c)
        {
            qu.push({it->first, len + it->second});
            it++;
        }
    }
    return 0;
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        a = (a % n + n) % n;
        int to = ((a + b) % n + n) % n;
        ve[a].emplace_back(to, (ll)b);
    }
    for (int i = 0; i < n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 0; i < n; i++)
        color_have[col[i]].push_back(i);
    for (int i = 0; i < n; i++)
    {
        sort(ve[i].begin(), ve[i].end(), [&](pair<int, ll> a, pair<int, ll> b)
             { return col[a.first] < col[b.first]; });
    }
    for (int i = 1; i <= num; i++)
        ok[i] = check_color(i);

    vector<int> cnt(num + 1);
    for (int i = 0; i < n; i++)
    {
        cout << "i=" << i << endl;
        for (auto [to, len] : ve[i])
        {
            int ci = col[i], ct = col[to];
            if (ci == ct)
                continue;
            cnt[ci]++;
            ve2[ct].push_back(ci);
            cout << "edge ct=" << ct << " ci=" << ci << endl;
        }
    }
    queue<int> qu;
    for (int i = 1; i <= num; i++)
        if (cnt[i])
            qu.push(i);
    while (!qu.empty())
    {
        int x = qu.front();
        cout << "topo x=" << x << " yes=" << ok[x] << endl;
        qu.pop();
        for (auto it : ve2[x])
        {
            cout << "x=" << x << " it=" << it << endl;
            ok[it] |= ok[x];
            if ((--cnt[it]) == 0)
                qu.push(it);
        }
    }
    while (q--)
    {
        int x;
        cin >> x;
        x = (x % n + x) % n;
        x = col[x];
        if (ok[x])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 7720kb

input:

2 1000 100 10 1
4
10
00

01
00

00
10

00
01
1
11
11

output:

i=0
i=1
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

wrong output format Expected integer, but "i=0" found