oj.uz

Submission #265459

# Submission time Handle Problem Language Result Execution time Memory
265459 2020-08-14T21:28:25 Z DS007 Duathlon (APIO18_duathlon) C++14
31 / 100
 368 ms 69072 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5, M = 2e5;
vector<int> adj[N], tree[N];
bool explored[N], up[N], down[N];
int n, m, dp[N][3], ans, cid[N], cnt[N], dep[N], sz[N], comp[N], compno;
set<pair<int, int>> br;

void dfs2(int v, int p = -1) {
    if (sz[v] == 0)
        return;

    explored[v] = true;
    int s1 = 0, s2 = 0;
    dp[v][0] = sz[v];
    dp[v][1] = sz[v] * (sz[v] - 1) - (sz[v] - 1);
    dp[v][2] = sz[v] * (sz[v] - 1) * (sz[v] - 2);

    for (int i : tree[v]) {
        if (i != p) {
            dfs2(i, v);
            dp[v][0] += dp[i][0];
            dp[v][1] += dp[i][0] * sz[v] + dp[i][1];
            dp[v][2] += dp[i][1] * sz[v] * 2 + (sz[v] * (sz[v] - 1) - (sz[v] - 1)) * dp[i][0] * 2;
            s2 += dp[i][1];
            s1 += dp[i][0];
        }
    }

    for (int i : tree[v]) {
        if (i != p) {
            s2 -= dp[i][1];
            s1 -= dp[i][0];
            dp[v][2] += s2 * dp[i][0] * 2;
            dp[v][2] += s1 * dp[i][0];
            s2 += dp[i][1];
            s1 += dp[i][0];
        }
    }

    ans += dp[v][2];
}

void dfs1(int v) {
    int curcmp = compno;
    comp[v] = curcmp;

    queue<int> q;
    q.push(v);
    explored[v] = true;

    while (!q.empty()) {
        int u = q.front();
        sz[curcmp]++;
        q.pop();

        for (int i : adj[u]) {
            if (explored[i])
                continue;

            if (br.count({u, i})) {
                compno++;
                tree[curcmp].push_back(compno);
                tree[compno].push_back(curcmp);
                dfs1(i);
            } else {
                q.push(i);
                explored[i] = true;
            }
        }
    }
}

void dfs(int v, int p = -1, int d = 0) {
    explored[v] = true;
    dep[v] = d;

    for (int i : adj[v]) {
        if (!explored[i])
            dfs(i, v, d + 1), cnt[v] += cnt[i];
        else if (i != p && dep[i] < dep[v])
            cnt[v]++;
        else if (i != p)
            cnt[v]--;
    }

    if (cnt[v] == 0 && p != -1)
        br.insert({p, v}), br.insert({v, p});
}

int solveTestCase() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 0; i < n; i++) {
        if (!explored[i])
            dfs(i);
        //cerr << cnt[i] << " ";
    }
    //cerr << "\n";
    //assert(br.size() == m * 2);

    //for (auto i : br)
    //  cerr << i.first << " " << i.second << "\n";

    fill(explored, explored + n, false);
    for (int i = 0; i < n; i++) {
        if (!explored[i])
            dfs1(i), compno++;
        //cerr << comp[i] << " " << sz[comp[i]] << "\n";
    }

    //for (int i = 0; i < n; i++)
    //    assert(sz[i] == 1);

    fill(explored, explored + n, false);
    assert(compno <= n);
    for (int i = 0; i < n; i++) {
        if (!explored[i])
            dfs2(i);
        //cerr << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
    }

    cout << ans;
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Incorrect 4 ms 5120 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 114 ms 20856 KB Output is correct
2 Correct 98 ms 20856 KB Output is correct
3 Correct 246 ms 51020 KB Output is correct
4 Correct 167 ms 32760 KB Output is correct
5 Correct 178 ms 36728 KB Output is correct
6 Correct 244 ms 45304 KB Output is correct
7 Correct 248 ms 35064 KB Output is correct
8 Correct 255 ms 37880 KB Output is correct
9 Correct 240 ms 29560 KB Output is correct
10 Correct 242 ms 29428 KB Output is correct
11 Correct 183 ms 19192 KB Output is correct
12 Correct 175 ms 19448 KB Output is correct
13 Correct 154 ms 19448 KB Output is correct
14 Correct 146 ms 18936 KB Output is correct
15 Correct 125 ms 18956 KB Output is correct
16 Correct 116 ms 18296 KB Output is correct
17 Correct 20 ms 10368 KB Output is correct
18 Correct 22 ms 10360 KB Output is correct
19 Correct 17 ms 10240 KB Output is correct
20 Correct 17 ms 10240 KB Output is correct
21 Correct 17 ms 10112 KB Output is correct
22 Correct 18 ms 10240 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5376 KB Output is correct
2 Correct 5 ms 5376 KB Output is correct
3 Correct 5 ms 5376 KB Output is correct
4 Correct 5 ms 5888 KB Output is correct
5 Correct 5 ms 5632 KB Output is correct
6 Correct 5 ms 5632 KB Output is correct
7 Correct 5 ms 5632 KB Output is correct
8 Correct 6 ms 5536 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 5 ms 5376 KB Output is correct
12 Correct 5 ms 5376 KB Output is correct
13 Correct 5 ms 5376 KB Output is correct
14 Correct 5 ms 5248 KB Output is correct
15 Correct 4 ms 5248 KB Output is correct
16 Correct 4 ms 5248 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 4 ms 5376 KB Output is correct
19 Correct 4 ms 5376 KB Output is correct
20 Correct 4 ms 5372 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 30848 KB Output is correct
2 Correct 301 ms 30952 KB Output is correct
3 Correct 279 ms 30712 KB Output is correct
4 Correct 289 ms 30716 KB Output is correct
5 Correct 281 ms 30800 KB Output is correct
6 Correct 368 ms 69072 KB Output is correct
7 Correct 363 ms 57080 KB Output is correct
8 Correct 350 ms 50300 KB Output is correct
9 Correct 341 ms 41724 KB Output is correct
10 Correct 366 ms 30712 KB Output is correct
11 Correct 325 ms 30844 KB Output is correct
12 Correct 328 ms 30776 KB Output is correct
13 Correct 317 ms 30712 KB Output is correct
14 Correct 304 ms 29152 KB Output is correct
15 Correct 255 ms 27256 KB Output is correct
16 Correct 153 ms 21752 KB Output is correct
17 Correct 278 ms 30240 KB Output is correct
18 Correct 270 ms 30180 KB Output is correct
19 Correct 248 ms 30756 KB Output is correct
20 Correct 239 ms 30276 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 30840 KB Output is correct
2 Correct 303 ms 30584 KB Output is correct
3 Incorrect 245 ms 24184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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