oj.uz

Submission #356276

# Submission time Handle Problem Language Result Execution time Memory
356276 2021-01-23T08:56:10 Z valerikk Duathlon (APIO18_duathlon) C++17
10 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 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) {
    vis[v] = true;
    low[v] = dep[v];
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            dep[u] = dep[v] + 1;
            dfs(u, i);
            low[v] = min(low[v], low[u]);
            if (dep[v] <= low[u] || p == -1) {
                col[i] = ++cnt;
            } else {
                col[i] = col[p];
            }
        } else {
            if (i != p) {
                low[v] = min(low[v], dep[u]);
                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);
            else
                ans -= (long long)sz[u] * (sz[u] - 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});
    }
    cnt = n;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dep[i] = 0;
            dfs(i);
        }
    }
    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 Runtime error 645 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 645 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 22008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5356 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 5 ms 5228 KB Output is correct
10 Correct 4 ms 5228 KB Output is correct
11 Correct 5 ms 5228 KB Output is correct
12 Correct 5 ms 5228 KB Output is correct
13 Correct 5 ms 5228 KB Output is correct
14 Correct 6 ms 5228 KB Output is correct
15 Correct 4 ms 5228 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 5 ms 5228 KB Output is correct
18 Correct 5 ms 5228 KB Output is correct
19 Correct 4 ms 5228 KB Output is correct
20 Correct 4 ms 5228 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 21484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Runtime error 760 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 21612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 645 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 645 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -