oj.uz

Submission #265448

# Submission time Handle Problem Language Result Execution time Memory
265448 2020-08-14T20:57:07 Z DS007 Duathlon (APIO18_duathlon) C++14
31 / 100
 423 ms 69624 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][1] * 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);
    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 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 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 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 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 120 ms 20856 KB Output is correct
2 Correct 118 ms 22008 KB Output is correct
3 Correct 231 ms 52348 KB Output is correct
4 Correct 184 ms 34040 KB Output is correct
5 Correct 248 ms 37880 KB Output is correct
6 Correct 278 ms 46584 KB Output is correct
7 Correct 258 ms 36392 KB Output is correct
8 Correct 240 ms 39160 KB Output is correct
9 Correct 269 ms 30872 KB Output is correct
10 Correct 283 ms 30840 KB Output is correct
11 Correct 167 ms 20216 KB Output is correct
12 Correct 167 ms 20344 KB Output is correct
13 Correct 149 ms 20216 KB Output is correct
14 Correct 158 ms 19832 KB Output is correct
15 Correct 130 ms 19576 KB Output is correct
16 Correct 139 ms 18936 KB Output is correct
17 Correct 17 ms 10368 KB Output is correct
18 Correct 17 ms 10368 KB Output is correct
19 Correct 18 ms 10240 KB Output is correct
20 Correct 21 ms 10240 KB Output is correct
21 Correct 17 ms 10112 KB Output is correct
22 Correct 17 ms 10112 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5376 KB Output is correct
2 Correct 6 ms 5376 KB Output is correct
3 Correct 6 ms 5376 KB Output is correct
4 Correct 6 ms 5888 KB Output is correct
5 Correct 5 ms 5632 KB Output is correct
6 Correct 6 ms 5632 KB Output is correct
7 Correct 6 ms 5632 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 6 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 5 ms 5248 KB Output is correct
16 Correct 4 ms 5248 KB Output is correct
17 Correct 4 ms 5376 KB Output is correct
18 Correct 6 ms 5376 KB Output is correct
19 Correct 5 ms 5376 KB Output is correct
20 Correct 4 ms 5376 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 30712 KB Output is correct
2 Correct 323 ms 31352 KB Output is correct
3 Correct 333 ms 31352 KB Output is correct
4 Correct 414 ms 31452 KB Output is correct
5 Correct 321 ms 31352 KB Output is correct
6 Correct 367 ms 69624 KB Output is correct
7 Correct 423 ms 57816 KB Output is correct
8 Correct 377 ms 50808 KB Output is correct
9 Correct 352 ms 42492 KB Output is correct
10 Correct 330 ms 31356 KB Output is correct
11 Correct 334 ms 31276 KB Output is correct
12 Correct 291 ms 31612 KB Output is correct
13 Correct 319 ms 31348 KB Output is correct
14 Correct 317 ms 29816 KB Output is correct
15 Correct 252 ms 27896 KB Output is correct
16 Correct 142 ms 22392 KB Output is correct
17 Correct 283 ms 30828 KB Output is correct
18 Correct 282 ms 30900 KB Output is correct
19 Correct 296 ms 31448 KB Output is correct
20 Correct 273 ms 30952 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5376 KB Output is correct
2 Correct 5 ms 5376 KB Output is correct
3 Incorrect 5 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 372 ms 30840 KB Output is correct
2 Correct 410 ms 31096 KB Output is correct
3 Incorrect 263 ms 25720 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 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 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 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 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 -