QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188325#5487. Movie NightZiadElGafy#WA 4ms19940kbC++202.5kb2023-09-25 18:57:392023-09-25 18:57:40

Judging History

你现在查看的是最新测评结果

  • [2023-09-25 18:57:40]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:19940kb
  • [2023-09-25 18:57:39]
  • 提交

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'