QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188325 | #5487. Movie Night | ZiadElGafy# | WA | 4ms | 19940kb | C++20 | 2.5kb | 2023-09-25 18:57:39 | 2023-09-25 18:57:40 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define el '\n'
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef __int128 bigInt;
using namespace std;
const int N = 4e5 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 21, SQ = 500;
int mul(int a, int b) {
return 1LL * a * b % mod;
}
int n, a[N], scc[N], lowLink[N], timer[N], compID, curTimer;
vector<int> g[N];
bool inStack[N];
stack<int> stk;
void tarjan(int node){
timer[node] = lowLink[node] = ++curTimer;
stk.push(node);
inStack[node] = 1;
for(auto &i : g[node]){
if(!timer[i]){
tarjan(i);
lowLink[node] = min(lowLink[node], lowLink[i]);
}
else if(inStack[i])
lowLink[node] = min(lowLink[node], timer[i]);
}
if(lowLink[node] == timer[node]){
compID++;
while(1){
int cur = stk.top();
stk.pop();
inStack[cur] = 0;
scc[cur] = compID;
if(cur == node)
break;
}
}
}
struct DSU{
int par[N], sz[N];
void init(int n){
for(int i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
}
int findPar(int v){
return (par[v] == v ? v : par[v] = findPar(par[v]));
}
void join(int u, int v){
u = findPar(u), v = findPar(v);
if(u == v)
return;
if(sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
}dsu;
void doWork() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
g[i].push_back(a[i]);
}
for (int i = 1; i <= n; i++) {
if (!scc[i]) {
tarjan(i);
}
}
dsu.init(compID);
for (int i = 1; i <= n; i++) {
int u = i, v = a[i];
dsu.join(scc[u], scc[v]);
}
unordered_set<int> vis;
int ans = 1;
for (int i = 1; i <= compID; i++) {
int par = dsu.findPar(i);
if (vis.find(par) != vis.end()) {
continue;
}
vis.insert(par);
ans = mul(ans, dsu.sz[par] + 1);
}
ans--;
if (ans < 0) {
ans += mod;
}
cout << ans << el;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tests = 1;
// cin >> tests;
for (int i = 1; i <= tests; i++) {
doWork();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 19840kb
input:
4 2 3 4 3
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 4ms
memory: 19908kb
input:
5 2 3 1 5 4
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 4ms
memory: 17860kb
input:
6 2 4 2 6 1 3
output:
3
result:
ok single line: '3'
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 19940kb
input:
8 2 3 4 1 3 3 1 4
output:
5
result:
wrong answer 1st lines differ - expected: '16', found: '5'