oj.uz

Submission #159449

# Submission time Handle Problem Language Result Execution time Memory
159449 2019-10-22T18:28:54 Z Minnakhmetov Duathlon (APIO18_duathlon) C++14
31 / 100
 146 ms 21140 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});
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, -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 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7456 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 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7456 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21120 KB Output is correct
2 Correct 92 ms 21140 KB Output is correct
3 Correct 97 ms 19152 KB Output is correct
4 Correct 95 ms 19832 KB Output is correct
5 Correct 91 ms 18936 KB Output is correct
6 Correct 99 ms 19704 KB Output is correct
7 Correct 92 ms 18424 KB Output is correct
8 Correct 98 ms 18912 KB Output is correct
9 Correct 104 ms 17656 KB Output is correct
10 Correct 97 ms 17912 KB Output is correct
11 Correct 83 ms 16568 KB Output is correct
12 Correct 80 ms 16248 KB Output is correct
13 Correct 77 ms 16124 KB Output is correct
14 Correct 75 ms 15864 KB Output is correct
15 Correct 55 ms 15224 KB Output is correct
16 Correct 56 ms 14968 KB Output is correct
17 Correct 11 ms 9464 KB Output is correct
18 Correct 11 ms 9464 KB Output is correct
19 Correct 11 ms 9464 KB Output is correct
20 Correct 12 ms 9464 KB Output is correct
21 Correct 11 ms 9464 KB Output is correct
22 Correct 11 ms 9464 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7520 KB Output is correct
2 Correct 8 ms 7480 KB Output is correct
3 Correct 8 ms 7548 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7548 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 8 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 8 ms 7416 KB Output is correct
13 Correct 8 ms 7516 KB Output is correct
14 Correct 9 ms 7544 KB Output is correct
15 Correct 8 ms 7544 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7548 KB Output is correct
18 Correct 8 ms 7544 KB Output is correct
19 Correct 8 ms 7544 KB Output is correct
20 Correct 8 ms 7544 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 16376 KB Output is correct
2 Correct 107 ms 16424 KB Output is correct
3 Correct 146 ms 16484 KB Output is correct
4 Correct 102 ms 16568 KB Output is correct
5 Correct 99 ms 16444 KB Output is correct
6 Correct 109 ms 20856 KB Output is correct
7 Correct 113 ms 19552 KB Output is correct
8 Correct 109 ms 18808 KB Output is correct
9 Correct 114 ms 17848 KB Output is correct
10 Correct 106 ms 16500 KB Output is correct
11 Correct 99 ms 16504 KB Output is correct
12 Correct 103 ms 16492 KB Output is correct
13 Correct 96 ms 16460 KB Output is correct
14 Correct 94 ms 16340 KB Output is correct
15 Correct 85 ms 15796 KB Output is correct
16 Correct 56 ms 14200 KB Output is correct
17 Correct 69 ms 16872 KB Output is correct
18 Correct 72 ms 16868 KB Output is correct
19 Correct 67 ms 17220 KB Output is correct
20 Correct 67 ms 16872 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 16476 KB Output is correct
2 Correct 95 ms 16248 KB Output is correct
3 Incorrect 112 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 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7456 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 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7456 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 -