oj.uz

Submission #356302

# Submission time Handle Problem Language Result Execution time Memory
356302 2021-01-23T09:13:54 Z valerikk Duathlon (APIO18_duathlon) C++17
31 / 100
 304 ms 35820 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]) {
            int val = (int)gr[u].size() - 1;
            if (u == p) {
                ans -= (long long) (S - sz[v]) * (S - sz[v] - 1);
                ans += (long long)val * (val - 1);
            } else {
                ans -= (long long) sz[u] * (sz[u] - 1);
                ans += (long long)val * (val - 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 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 30684 KB Output is correct
2 Correct 129 ms 31844 KB Output is correct
3 Correct 186 ms 32100 KB Output is correct
4 Correct 146 ms 30820 KB Output is correct
5 Correct 150 ms 29284 KB Output is correct
6 Correct 182 ms 30952 KB Output is correct
7 Correct 187 ms 29036 KB Output is correct
8 Correct 205 ms 29420 KB Output is correct
9 Correct 180 ms 27500 KB Output is correct
10 Correct 153 ms 27884 KB Output is correct
11 Correct 138 ms 25196 KB Output is correct
12 Correct 143 ms 24940 KB Output is correct
13 Correct 125 ms 24812 KB Output is correct
14 Correct 104 ms 24428 KB Output is correct
15 Correct 86 ms 23276 KB Output is correct
16 Correct 89 ms 23020 KB Output is correct
17 Correct 12 ms 15724 KB Output is correct
18 Correct 12 ms 15724 KB Output is correct
19 Correct 12 ms 15724 KB Output is correct
20 Correct 12 ms 15724 KB Output is correct
21 Correct 13 ms 15724 KB Output is correct
22 Correct 12 ms 15724 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 26732 KB Output is correct
2 Correct 196 ms 28012 KB Output is correct
3 Correct 220 ms 28012 KB Output is correct
4 Correct 195 ms 28032 KB Output is correct
5 Correct 191 ms 28012 KB Output is correct
6 Correct 238 ms 35820 KB Output is correct
7 Correct 251 ms 33388 KB Output is correct
8 Correct 237 ms 31852 KB Output is correct
9 Correct 229 ms 30572 KB Output is correct
10 Correct 198 ms 28012 KB Output is correct
11 Correct 176 ms 28012 KB Output is correct
12 Correct 173 ms 28012 KB Output is correct
13 Correct 205 ms 28016 KB Output is correct
14 Correct 142 ms 27116 KB Output is correct
15 Correct 128 ms 26220 KB Output is correct
16 Correct 89 ms 23208 KB Output is correct
17 Correct 153 ms 28644 KB Output is correct
18 Correct 140 ms 28508 KB Output is correct
19 Correct 158 ms 28372 KB Output is correct
20 Correct 151 ms 28636 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 26732 KB Output is correct
2 Correct 222 ms 27884 KB Output is correct
3 Incorrect 304 ms 27628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -