QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #873941 | #9677. 基础博弈练习题 | A_programmer | 0 | 64ms | 102396kb | C++17 | 2.4kb | 2025-01-27 09:48:37 | 2025-01-27 09:48:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn], q[maxn], in[maxn], ans[maxn], n;
vector<int> g[maxn], vec[maxn], p[maxn];
bool vis[maxn];
int dfn[maxn], low[maxn], cnt;
int ind[maxn], stk[maxn], tp, dot;
void tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
stk[++tp] = u;
for (int v : g[u])
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (!ind[v]) low[u] = min(low[u], dfn[v]);
if (low[u] == dfn[u])
{
ind[u] = ++dot, vec[dot].emplace_back(u);
while (stk[tp] != u) ind[stk[tp]] = dot, vec[dot].emplace_back(stk[tp]), tp--;
tp--;
}
}
void Topo()
{
int hd = 1, tl = 0;
for (int i = 1; i <= dot; i++) if (!in[i]) q[++tl] = i;
while (hd <= tl)
{
int u = q[hd++];
for (int v : p[u])
if (--in[v] == 0) q[++tl] = v;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int m, k; cin >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= k; i++) cin >> b[i];
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
g[u].emplace_back(v);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; u++)
for (int v : g[u]) if (ind[u] != ind[v]) p[ind[u]].emplace_back(ind[v]), in[ind[v]]++;
Topo();
for (int i = dot; i; i--)
{
int id = q[i]; ans[id] = inf;
for (int v : p[id])
{
ans[id] = min(ans[id], ans[v]);
if (vec[v].size() == 1 && ans[v] > a[vec[v][0]]) ans[id] = min(ans[id], a[vec[v][0]] - 1);
}
int mn = inf;
for (int u : vec[id])
{
vis[a[u]] = 1;
mn = min(mn, a[u]);
}
if (mn > ans[id]) continue;
int pos = mn;
while (pos <= k && pos <= ans[id] && vis[pos]) pos++; pos--;
for (int u : vec[id]) vis[a[u]] = 0;
if (pos == ans[id] && mn != pos) ans[id] = min(ans[id], mn + ((mn ^ pos ^ 1) & 1) - 1);
else if (pos != ans[id] && vec[id].size() > 1) ans[id] = min(ans[id], mn + ((mn ^ pos) & 1) - 1);
}
for (int i = 1; i <= n; i++) cout << (ans[ind[i]] == inf ? -1 : ans[ind[i]]) << " ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 85740kb
input:
83 93 13 8 9 10 7 7 7 6 3 1 10 6 2 5 7 1 3 4 2 1 10 7 4 8 9 2 2 1 9 2 5 1 7 8 6 1 9 9 10 4 1 2 9 2 3 4 2 9 10 8 1 4 1 8 4 1 4 4 7 4 8 2 9 2 5 2 2 3 3 8 5 2 9 3 10 8 8 1 6 6 1 6 7 10 7 5 10 3 2 2 7 4 8 7 6 6 5 56 36 33 41 32 62 37 7 6 53 41 13 9 36 44 77 38 62 76 16 72 5 40 13 55 60 5 78 72 45 13 44 ...
output:
0 -1 -1 -1 1 0 -1 3 0 -1 0 -1 0 0 2 -1 0 -1 0 0 -1 0 -1 1 -1 -1 -1 -1 -1 -1 0 0 0 -1 0 -1 2 0 0 0 0 0 -1 0 -1 -1 0 0 0 -1 0 0 0 0 0 0 -1 -1 0 -1 0 0 0 0 0 7 -1 0 0 -1 -1 1 1 1 -1 1 -1 2 0 0 0 0 0
result:
wrong answer 5th numbers differ - expected: '2', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 64ms
memory: 102396kb
input:
100000 355071 10000 5 7 4 7 4 1 10 5 9 4 9 4 3 10 5 4 9 1 7 10 1 6 10 3 10 9 8 4 6 3 10 8 6 8 3 5 10 9 7 7 1 3 8 8 6 2 8 4 2 9 1 10 3 6 3 8 9 10 5 7 3 2 1 5 7 4 3 4 6 4 2 7 2 5 5 6 4 6 7 4 4 6 4 2 3 9 9 9 10 8 1 6 7 2 9 8 2 3 1 6 9 4 10 3 10 1 2 3 3 4 1 1 1 5 8 6 8 3 1 6 2 9 5 9 4 7 2 10 7 5 2 2 7 4...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 383rd numbers differ - expected: '9', found: '7'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%