oj.uz

Submission #159447

# Submission time Handle Problem Language Result Execution time Memory
159447 2019-10-22T18:26:47 Z Minnakhmetov Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 459688 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 7 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 7 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 94 ms 21292 KB Output is correct
2 Correct 96 ms 21112 KB Output is correct
3 Correct 93 ms 19164 KB Output is correct
4 Execution timed out 1117 ms 459688 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 8 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 9 ms 7544 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct
11 Correct 8 ms 7416 KB Output is correct
12 Correct 9 ms 7548 KB Output is correct
13 Correct 8 ms 7544 KB Output is correct
14 Correct 8 ms 7544 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7544 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 95 ms 16436 KB Output is correct
2 Correct 96 ms 16472 KB Output is correct
3 Correct 101 ms 16496 KB Output is correct
4 Correct 102 ms 16376 KB Output is correct
5 Correct 102 ms 16348 KB Output is correct
6 Correct 112 ms 20856 KB Output is correct
7 Correct 112 ms 19552 KB Output is correct
8 Correct 150 ms 18680 KB Output is correct
9 Correct 108 ms 17912 KB Output is correct
10 Correct 97 ms 16464 KB Output is correct
11 Correct 100 ms 16500 KB Output is correct
12 Correct 95 ms 16376 KB Output is correct
13 Correct 94 ms 16376 KB Output is correct
14 Correct 85 ms 15736 KB Output is correct
15 Correct 78 ms 15096 KB Output is correct
16 Correct 53 ms 13432 KB Output is correct
17 Correct 71 ms 16876 KB Output is correct
18 Correct 76 ms 17000 KB Output is correct
19 Correct 84 ms 17252 KB Output is correct
20 Correct 96 ms 16872 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 7416 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 150 ms 16364 KB Output is correct
2 Correct 116 ms 16288 KB Output is correct
3 Incorrect 201 ms 16720 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 7 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 7 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 -