oj.uz

Submission #356289

# Submission time Handle Problem Language Result Execution time Memory
356289 2021-01-23T09:08:38 Z valerikk Duathlon (APIO18_duathlon) C++17
0 / 100
 232 ms 30564 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;

int n, m;
vector<pair<int, int>> g[N];
vector<int> gr[N];
int dep[N], low[N];
bool vis[N];
int col[N], cnt;
int sz[N];
long long ans;
int S;

void dfs(int v, int p = -1) {
    low[v] = dep[v];
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            dep[u] = dep[v] + 1;
            dfs(u, i);
            low[v] = min(low[v], low[u]);
        } else {
            if (i != p)
                low[v] = min(low[v], dep[u]);
        }
    }
}

void paint(int v, int p = -1) {
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            if (dep[v] <= low[u]) {
                col[i] = ++cnt;
            } else {
                col[i] = col[p];
            }
            paint(u, i);
        } else {
            if (i != p) {
                if (dep[u] < dep[v]) col[i] = col[p];
            }
        }
    }
}

int get_size(int v, int p = -1) {
    sz[v] = v <= n;
    for (int u : gr[v]) {
        if (u != p) {
            sz[v] += get_size(u, v);
        }
    }
    return sz[v];
}

void find_ans(int v, int p = -1) {
    vis[v] = true;
    for (int u : gr[v]) {
        if (u != p)
            find_ans(u, v);
    }
    if (v <= n) {
        for (int u : gr[v]) {
            if (u == p)
                ans -= (long long)(S - sz[v]) * (S - sz[v] - 1) - (long long)gr[u].size() * ((int)gr[u].size() - 1);
            else
                ans -= (long long)sz[u] * (sz[u] - 1) - (long long)gr[u].size() * ((int)gr[u].size() - 1);
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dep[i] = 0;
            dfs(i);
        }
    }
    for (int i = 1; i <= n; ++i)
        vis[i] = false;
    cnt = n;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            paint(i);
        }
    }/*
    for (int i = 1; i <= m; ++i)
        cout << col[i] << " ";
    cout << endl;
    return 0;*/
    for (int i = 1; i <= n; ++i) {
        vector<int> v;
        for (auto [u, i] : g[i])
            v.push_back(col[i]);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for (int c : v) {
            // cout << min(i, c) << " " << max(i, c) << endl;
            gr[i].push_back(c);
            gr[c].push_back(i);
        }
    }
    for (int i = 1; i <= cnt; ++i) {
        if (!vis[i]) {
            S = get_size(i);
            ans += (long long)S * (S - 1) * (S - 2);
            find_ans(i);
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 30564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 14572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 26764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 26732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -