QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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";
}
}
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