QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188295 | #5487. Movie Night | Beevo# | WA | 0ms | 3792kb | C++20 | 2.5kb | 2023-09-25 18:28:49 | 2023-09-25 18:28:49 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 1e9 + 7;
int mul(int a, int b) {
return 1LL * a * b % M;
}
int add(int a, int b) {
b = (b + M) % M;
return (a + b) % M;
}
vector<vector<int>> adj, adj_rev;
vector<bool> used;
vector<int> order, component;
void dfs1(int v) {
used[v] = true;
for (auto u : adj[v])
if (!used[u])
dfs1(u);
order.push_back(v);
}
void dfs2(int v) {
used[v] = true;
component.push_back(v);
for (auto u : adj_rev[v])
if (!used[u])
dfs2(u);
}
int dfs(int u, vector<vector<int>> &g) {
if (g[u].empty())
return 0;
return dfs(g[u][0], g) + 1;
}
void testCase() {
int n;
cin >> n;
adj.resize(n), adj_rev.resize(n);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
a--;
adj[i].push_back(a);
adj_rev[a].push_back(i);
}
used.assign(n, false);
for (int i = 0; i < n; i++)
if (!used[i])
dfs1(i);
used.assign(n, false);
reverse(order.begin(), order.end());
vector<int> roots(n, 0);
vector<int> root_nodes;
vector<vector<int>> adj_scc(n);
for (auto v : order)
if (!used[v]) {
dfs2(v);
int root = component.front();
for (auto u : component) roots[u] = root;
root_nodes.push_back(root);
component.clear();
}
vector<int> in(n);
for (int v = 0; v < n; v++)
for (auto u : adj[v]) {
int root_v = roots[v],
root_u = roots[u];
if (root_u != root_v)
adj_scc[root_u].push_back(root_v), in[root_v]++;
}
int sol = 1;
for (int i = 0; i < n; i++) {
if (!in[i] && roots[i] == i) {
if (adj_scc[i].empty()) {
sol = mul(sol, 2);
continue;
}
int cur = 1;
for (auto &j: adj_scc[i])
cur = mul(cur, dfs(j, adj_scc) + 1);
sol = mul(sol, add(cur, 2));
}
}
cout << add(sol, -1);
}
signed main() {
Beevo
int t = 1;
// cin >> t;
while (t--)
testCase();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
4 2 3 4 3
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 2 3 1 5 4
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
6 2 4 2 6 1 3
output:
3
result:
ok single line: '3'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3792kb
input:
8 2 3 4 1 3 3 1 4
output:
2
result:
wrong answer 1st lines differ - expected: '16', found: '2'