QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188557 | #5487. Movie Night | Gamal74# | WA | 0ms | 19048kb | C++20 | 2.3kb | 2023-09-25 23:56:45 | 2023-09-25 23:56:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl
void Gamal() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Clion
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 2e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
vector<int> adj[N], adjr[N], scc[N];
int vis[N], head[N], n, cnt;
stack<int> topo;
void dfs(int u) {
vis[u] = 1;
for (auto v: adj[u]) if (!vis[v]) dfs(v);
topo.push(u);
}
void dfs2(int u, int g) {
if (~head[u]) return;
head[u] = g;
for (auto v: adjr[u]) dfs2(v, g);
}
void dfs3(int u) {
cnt++;
for (auto v: scc[u])dfs3(v);
}
void kosaraju() {
for (int i = 0; i < n; ++i) {
vis[i] = false;
head[i] = -1;
}
int comps = 0;
for (int i = 0; i < n; i++)if (!vis[i]) dfs(i);
while (!topo.empty()) {
int u = topo.top();
topo.pop();
if (head[u] == -1) dfs2(u, comps++);
}
vector<int> in(n);
for (int u = 0; u < n; ++u) {
for (auto v: adj[u]) {
if (head[u] == head[v])continue;
scc[head[u]].push_back(head[v]);
in[head[v]]++;
}
}
ll ans = 1;
for (int i = 0; i < comps; ++i) {
if (in[i] == 0) {
cnt = 1;
dfs3(i);
ans = ans * cnt % MOD;
}
}
cout << (ans - 1 + MOD) % MOD;
}
void solve() {
cin >> n;
for (int i = 0; i < n; ++i) {
int y;
cin >> y;
y--;
adj[i].push_back(y);
adjr[y].push_back(i);
}
kosaraju();
}
signed main() {
Gamal();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 18476kb
input:
4 2 3 4 3
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 18096kb
input:
5 2 3 1 5 4
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 19048kb
input:
6 2 4 2 6 1 3
output:
3
result:
ok single line: '3'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 18940kb
input:
8 2 3 4 1 3 3 1 4
output:
80
result:
wrong answer 1st lines differ - expected: '16', found: '80'