oj.uz

Submission #159435

# Submission time Handle Problem Language Result Execution time Memory
159435 2019-10-22T17:11:04 Z Minnakhmetov Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 511864 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int to, i;
};

const int N = 1e5 + 5;
vector<E> g[N];
vector<int> g2[N], t[N];
int tin[N], mt[N], col[N], sz[N], sum[N];
int timer = 0, n, m;
bool used[N];

void dfs(int node, int anc) {
    used[node] = 1;
    tin[node] = ++timer;
    mt[node] = tin[node];
    for (E e : g[node]) {
        if (e.i != anc) {

            if (!used[e.to]) {
                dfs(e.to, e.i);
            }

            mt[node] = min(mt[node], mt[e.to]);

            if (mt[e.to] <= tin[node]) {
                g2[node].push_back(e.to);
                g2[e.to].push_back(node);
            }
        }
    }
}

void deep(int node, int c) {
    col[node] = c;
    used[node] = 1;

    sz[col[node]]++;

    for (int to : g2[node]) {
        if (!used[to]) {
            deep(to, c);
        }
    }

    for (E e : g[node]) {
        if (used[e.to] && col[e.to] != col[node]) {
            t[col[node]].push_back(col[e.to]);
            t[col[e.to]].push_back(col[node]);
        }
    }
}

ll ans = 0;

int walk(int node, int anc) {
    int s = sz[node];
    for (int to : t[node]) {
        if (to != anc) {
            s += walk(to, node);
        }
    }
    return s;
}

void dive(int node, int anc, int whole) {
    ans += sz[node] * (ll)(sz[node] - 1) * (sz[node] - 2);

    sum[node] = sz[node];

    used[node] = 1;

    for (int to : t[node]) {
        if (to != anc) {
            dive(to, node, whole);
            sum[node] += sum[to];
        }
    }

    for (int to : t[node]) {
        int s = 0;
        if (to == anc)
            s = whole - sum[node];
        else
            s = sum[to];

        ans += sz[node] * (ll)s * (whole - s - sz[node]);

        ans += (sz[node] * (ll)(sz[node] - 1) - sz[node] + 1) * s * 2;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    dfs(0, -1);

    int cc = 0;

    fill(used, used + n, 0);

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            deep(i, cc++);
        }
    }

    fill(used, used + cc, 0);

    for (int i = 0; i < cc; i++) {
        if (!used[i]) {
            dive(i, -1, walk(i, -1));
        }
    }

    cout << ans;


    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21264 KB Output is correct
2 Correct 100 ms 21212 KB Output is correct
3 Correct 95 ms 19192 KB Output is correct
4 Execution timed out 1111 ms 511864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 9 ms 7616 KB Output is correct
7 Correct 9 ms 7644 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 8 ms 7544 KB Output is correct
10 Correct 8 ms 7548 KB Output is correct
11 Correct 8 ms 7544 KB Output is correct
12 Correct 11 ms 7544 KB Output is correct
13 Correct 11 ms 7544 KB Output is correct
14 Correct 9 ms 7472 KB Output is correct
15 Correct 8 ms 7544 KB Output is correct
16 Correct 9 ms 7440 KB Output is correct
17 Correct 9 ms 7432 KB Output is correct
18 Correct 9 ms 7544 KB Output is correct
19 Correct 9 ms 7544 KB Output is correct
20 Correct 9 ms 7544 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 16380 KB Output is correct
2 Correct 167 ms 16504 KB Output is correct
3 Correct 160 ms 16412 KB Output is correct
4 Correct 103 ms 16376 KB Output is correct
5 Correct 107 ms 16376 KB Output is correct
6 Correct 116 ms 20856 KB Output is correct
7 Correct 112 ms 19452 KB Output is correct
8 Correct 106 ms 18652 KB Output is correct
9 Correct 116 ms 17800 KB Output is correct
10 Correct 142 ms 16348 KB Output is correct
11 Correct 111 ms 17836 KB Output is correct
12 Correct 97 ms 17656 KB Output is correct
13 Correct 95 ms 17668 KB Output is correct
14 Correct 79 ms 16760 KB Output is correct
15 Correct 74 ms 16120 KB Output is correct
16 Correct 49 ms 14072 KB Output is correct
17 Correct 70 ms 18284 KB Output is correct
18 Correct 67 ms 18120 KB Output is correct
19 Correct 69 ms 18400 KB Output is correct
20 Correct 77 ms 18152 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 16476 KB Output is correct
2 Correct 107 ms 16248 KB Output is correct
3 Incorrect 109 ms 16760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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