QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789270 | #9802. Light Up the Grid | ucup-team5071# | WA | 3ms | 7720kb | C++20 | 3.4kb | 2024-11-27 19:43:08 | 2024-11-27 19:43:08 |
Judging History
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