oj.uz

Submission #265469

# Submission time Handle Problem Language Result Execution time Memory
265469 2020-08-14T21:40:04 Z DS007 Duathlon (APIO18_duathlon) C++14
31 / 100
 406 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);
    assert(compno <= n);
    for (int i = 0; i < compno; i++) {
        if (!explored[i])
            dfs2(i);
        assert(sz[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 3 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 3 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 3 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 3 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 87 ms 20856 KB Output is correct
2 Correct 98 ms 20744 KB Output is correct
3 Correct 225 ms 51192 KB Output is correct
4 Correct 170 ms 32760 KB Output is correct
5 Correct 170 ms 36600 KB Output is correct
6 Correct 249 ms 45272 KB Output is correct
7 Correct 266 ms 35068 KB Output is correct
8 Correct 303 ms 37880 KB Output is correct
9 Correct 253 ms 29604 KB Output is correct
10 Correct 226 ms 29432 KB Output is correct
11 Correct 148 ms 19192 KB Output is correct
12 Correct 154 ms 19192 KB Output is correct
13 Correct 144 ms 19320 KB Output is correct
14 Correct 143 ms 18936 KB Output is correct
15 Correct 122 ms 18808 KB Output is correct
16 Correct 104 ms 18296 KB Output is correct
17 Correct 18 ms 10368 KB Output is correct
18 Correct 17 ms 10368 KB Output is correct
19 Correct 17 ms 10240 KB Output is correct
20 Correct 22 ms 10240 KB Output is correct
21 Correct 17 ms 10112 KB Output is correct
22 Correct 18 ms 10112 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 6 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 5 ms 5504 KB Output is correct
9 Correct 6 ms 5504 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 7 ms 5376 KB Output is correct
12 Correct 8 ms 5376 KB Output is correct
13 Correct 8 ms 5376 KB Output is correct
14 Correct 6 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 5 ms 5376 KB Output is correct
18 Correct 5 ms 5376 KB Output is correct
19 Correct 5 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 305 ms 30616 KB Output is correct
2 Correct 319 ms 30712 KB Output is correct
3 Correct 283 ms 30712 KB Output is correct
4 Correct 342 ms 30712 KB Output is correct
5 Correct 366 ms 30840 KB Output is correct
6 Correct 406 ms 68984 KB Output is correct
7 Correct 369 ms 57208 KB Output is correct
8 Correct 360 ms 50156 KB Output is correct
9 Correct 349 ms 41724 KB Output is correct
10 Correct 334 ms 30840 KB Output is correct
11 Correct 372 ms 30712 KB Output is correct
12 Correct 300 ms 30716 KB Output is correct
13 Correct 292 ms 30712 KB Output is correct
14 Correct 266 ms 28920 KB Output is correct
15 Correct 252 ms 27312 KB Output is correct
16 Correct 142 ms 21752 KB Output is correct
17 Correct 323 ms 30204 KB Output is correct
18 Correct 309 ms 30184 KB Output is correct
19 Correct 266 ms 30672 KB Output is correct
20 Correct 310 ms 30184 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 311 ms 30668 KB Output is correct
2 Correct 289 ms 30456 KB Output is correct
3 Incorrect 231 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 3 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 3 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 3 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 3 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 -