QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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";
    }
}

详细

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