oj.uz

Submission #265456

# Submission time Handle Problem Language Result Execution time Memory
265456 2020-08-14T21:14:54 Z DS007 Duathlon (APIO18_duathlon) C++14
31 / 100
 485 ms 68984 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);
    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 5096 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Incorrect 5 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 5096 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Incorrect 5 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 122 ms 20748 KB Output is correct
2 Correct 119 ms 20856 KB Output is correct
3 Correct 301 ms 51064 KB Output is correct
4 Correct 183 ms 32760 KB Output is correct
5 Correct 214 ms 36724 KB Output is correct
6 Correct 251 ms 45304 KB Output is correct
7 Correct 241 ms 35192 KB Output is correct
8 Correct 243 ms 37936 KB Output is correct
9 Correct 247 ms 29560 KB Output is correct
10 Correct 261 ms 29432 KB Output is correct
11 Correct 155 ms 19320 KB Output is correct
12 Correct 155 ms 19336 KB Output is correct
13 Correct 132 ms 19320 KB Output is correct
14 Correct 143 ms 18936 KB Output is correct
15 Correct 110 ms 18936 KB Output is correct
16 Correct 140 ms 18296 KB Output is correct
17 Correct 17 ms 10360 KB Output is correct
18 Correct 17 ms 10368 KB Output is correct
19 Correct 17 ms 10240 KB Output is correct
20 Correct 17 ms 10240 KB Output is correct
21 Correct 25 ms 10088 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 5 ms 5280 KB Output is correct
2 Correct 5 ms 5376 KB Output is correct
3 Correct 5 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 7 ms 5632 KB Output is correct
7 Correct 5 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 5 ms 5376 KB Output is correct
11 Correct 6 ms 5504 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 5 ms 5248 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 5 ms 5376 KB Output is correct
19 Correct 6 ms 5376 KB Output is correct
20 Correct 5 ms 5376 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 30652 KB Output is correct
2 Correct 369 ms 30636 KB Output is correct
3 Correct 360 ms 30712 KB Output is correct
4 Correct 310 ms 30712 KB Output is correct
5 Correct 363 ms 30712 KB Output is correct
6 Correct 385 ms 68984 KB Output is correct
7 Correct 485 ms 57208 KB Output is correct
8 Correct 458 ms 50168 KB Output is correct
9 Correct 383 ms 41852 KB Output is correct
10 Correct 362 ms 30712 KB Output is correct
11 Correct 366 ms 30712 KB Output is correct
12 Correct 370 ms 30716 KB Output is correct
13 Correct 305 ms 30712 KB Output is correct
14 Correct 337 ms 28920 KB Output is correct
15 Correct 298 ms 27256 KB Output is correct
16 Correct 168 ms 21752 KB Output is correct
17 Correct 274 ms 30184 KB Output is correct
18 Correct 266 ms 30312 KB Output is correct
19 Correct 287 ms 30944 KB Output is correct
20 Correct 252 ms 30436 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 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 302 ms 30712 KB Output is correct
2 Correct 347 ms 30460 KB Output is correct
3 Incorrect 310 ms 24312 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 5096 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Incorrect 5 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 5096 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Incorrect 5 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -