QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188553#5487. Movie Nightbeshoyhany#WA 5ms18988kbC++203.0kb2023-09-25 23:43:142023-09-25 23:43:15

Judging History

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

  • [2023-09-25 23:43:15]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:18988kb
  • [2023-09-25 23:43:14]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    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
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

int n;
vector<int> adj[N], adj_r[N], adj_scc[N], topo;
bool vis[N];

void dfs1(int u) {

    vis[u] = true;

    for (auto v: adj[u]) {
        if (vis[v])continue;
        dfs1(v);
    }

    topo.pp(u);
}

int comp[N];

void dfs2(int u, int cur) {

    vis[u] = true;
    comp[u] = cur;

    for (auto v: adj_r[u]) {
        if (vis[v])continue;
        dfs2(v, cur);
    }
}

int c;

void scc() {

    for (int i = 0; i < n; ++i) {
        if (!vis[i])
            dfs1(i);
    }

    reverse(all(topo));

    memset(vis, false, sizeof vis);


    for (int i = 0; i < topo.size(); ++i) {
        if (!vis[topo[i]])
            dfs2(topo[i], c++);
    }

    for (int i = 0; i < n; ++i) {
        for (auto v: adj[i]) {
            if (comp[i] != comp[v]) {
                adj_scc[comp[i]].pp(comp[v]);
            }
        }
    }
}

int par[N], sz[N];

void init() {
    for (int i = 0; i < n; ++i) {
        par[i] = i;
        sz[i] = 1;
    }
}

int get(int u) {
    return par[u] == u ? u : par[u] = get(par[u]);
}

void join(int x, int y) {
    int u = get(x), v = get(y);
    if (u == v)return;
    if (sz[u] > sz[v])
        swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        x--;
        adj[i].pp(x);
        adj_r[x].pp(i);
    }
    scc();
    init();
    for (int i = 0; i < c; ++i) {
        for(auto v : adj_scc[i])join(i, v);
    }
    vector<int>freq(c);
    for (int i = 0; i < c; ++i) {
        freq[get(i)] ++;
    }
    int ans = 1;
    for (int i = 0; i < c; ++i) {
        ans = mul(ans, freq[i] + 1);
    }
    cout << add(ans, -1);
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 18988kb

input:

4
2
3
4
3

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 18156kb

input:

5
2
3
1
5
4

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 5ms
memory: 17892kb

input:

6
2
4
2
6
1
3

output:

3

result:

ok single line: '3'

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 18148kb

input:

8
2
3
4
1
3
3
1
4

output:

5

result:

wrong answer 1st lines differ - expected: '16', found: '5'