oj.uz

Submission #252144

# Submission time Handle Problem Language Result Execution time Memory
252144 2020-07-24T10:20:03 Z Mlxa Duathlon (APIO18_duathlon) C++14
18 / 100
 1000 ms 112632 KB 
#include <bits/stdc++.h>
using ll = long long;
#define int ll
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
using namespace std;

const int N = 2e5 + 10;

void umin(int &a, int b) {
    a = min(a, b);
}
void umax(int &a, int b) {
    a = max(a, b);
}

int n;
int m;
vector<int> g[N];
int con[N];
int bycon[N];
int curcon = 0;
int timer  = 0;
int in[N];
int up[N];
int sz[N];
bool cp[N];
int pr[N];
bool used[N];

void cutpoints(int v, int p) {
    assert(con[v] == -1);
    con[v] = curcon;
    in[v] = up[v] = timer++;
    sz[v] = 1;
    pr[v] = p;
    int soncnt = 0;
    for (int u : g[v]) {
        if (con[u] == -1) {
            ++soncnt;
            cutpoints(u, v);
            umin(up[v], up[u]);
            cp[v] |= in[v] <= up[u];
            sz[v] += sz[u];
        } else if (u != p) {
            umin(up[v], in[u]);
        }
    }
    if (p == -1) {
        cp[v] = soncnt >= 2;
    }
}

int newc = 0;

vector<int> vertex[N];
map<int, int> bycol[N];
int maxcol[N];
set<int> colors[N];
map<int, int> without[N];
map<int, int> without2[N];

void edge(int v, int u, int c) {
    //cerr << "edge " << v + 1 << " " << u + 1 << " " << c + 1 << endl;
    vertex[c].push_back(v);
    vertex[c].push_back(u);
    umax(maxcol[v], c);
    umax(maxcol[u], c);
    colors[v].insert(c);
    colors[u].insert(c);
}

void paint(int v, int c) {
    used[v] = true;
    bycol[v][c] += bycon[con[v]] - sz[v];
    for (int u : g[v]) {
        if (u == pr[v]) {
            continue;
        }
        if (!used[u]) {
            if (in[v] <= up[u]) {
                edge(v, u, newc);
                bycol[v][newc] += sz[u];
                paint(u, newc++);
            } else {
                edge(v, u, c);
                paint(u, c);
            }
        } else if (in[u] < in[v]) {
            edge(v, u, c);
        }
    }
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif // LC
    ios::sync_with_stdio(0);
    cin.tie(0);
    fill_n(con, N, -1);
    cin >> n >> m;
    for (int v, u, i = 0; i < m; ++i) {
        cin >> v >> u;
        --v;
        --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    for (int i = 0; i < n; ++i) {
        if (con[i] != -1) {
            continue;
        }
        cutpoints(i, -1);
        ++curcon;
    }
    for (int i = 0; i < n; ++i) {
        ++bycon[con[i]];
    }
    /*for (int i = 0; i < n; ++i) {
        cerr << cp[i];
    }
    cerr << endl;*/
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            paint(i, newc++);
        }
    }
    int answer = 0;
    for (int i = 0; i < newc; ++i) {
        sort(all(vertex[i]));
        vertex[i].erase(unique(all(vertex[i])), vertex[i].end());
        int cur = (int)vertex[i].size();
        if (!cur) {
            continue;
        }
        answer += cur * (cur - 1) * (cur - 2);
        vector<int> oth;
        for (int v : vertex[i]) {
            int s = 0;
            int s2 = 0;
            for (auto e : bycol[v]) {
                if (e.x != i) {
                    s += e.y;
                    if (vertex[e.x].size()) {
                        s2 += (int)vertex[e.x].size() - 1;
                    }
                }
            }
            if (s) {
                without[v][i] = s;
                without2[v][i] = s2;
                oth.push_back(s);
            }
        }
        /*
        cerr << i + 1 << ":\t";
        for (int e : oth) {
            cerr << e << " ";
        }
        cerr << endl;*/
        int cn = con[vertex[i][0]];
        //cerr << "\t\t###\t\t" << cur << " " << bycon[cn] - cur << endl;
        answer += 2 * (cur - 1) * (cur - 1) * (bycon[cn] - cur);
        cur = 0;
        for (int v : vertex[i]) {
            cur += (maxcol[v] == i) && (!cp[v]);
        }
        int half = 0;
        int pref = 0;
        //cerr << "---" << endl;
        for (int e : oth) {
           //     cerr << e << " ";
            half += cur * pref * e;
            pref += e;
        }
        //cerr << endl;
        //cerr << i << " " << cur << " " << half << endl;
        answer += 2 * half;
    }
    for (int i = 0; i < n; ++i) {
        //cerr << i + 1 << "\t" << without[i][maxcol[i]] << " " << without2[i][maxcol[i]] << endl;
        if (colors[i].empty()) {
            continue;
        }
        vector<int> oth;
        for (int c : colors[i]) {
            assert(vertex[c].size() > 0);
            oth.push_back((int)vertex[c].size() - 1);
        }
        int pref = 0;
        int half = 0;
        for (int e : oth) {
            half += pref * e;
            pref += e;
        }
        answer -= 2 * half;

        int part;
        int small;
        if (!cp[i]) {
            int mcs = -1;
            vector<pair<int, int>> oth2;
            for (int c : colors[i]) {
                assert(vertex[c].size() > 0);
                if (c != maxcol[i]) {
                    oth2.emplace_back((int)vertex[c].size() - 1, bycol[i][c]);
                } else {
                    mcs = (int)vertex[c].size();
                }
            }
            assert(mcs != -1);
            part = without[i][maxcol[i]];
            small = without2[i][maxcol[i]];
            answer -= 2 * small * (bycon[con[i]] - mcs - part);
        }

        oth.clear();
        for (int c : colors[i]) {
            part = bycol[i][c];
            small = max(0LL, (int)vertex[c].size() - 1);
            oth.push_back(part - small);
        }
        pref = 0;
        half = 0;
        for (int e : oth) {
            half += pref * e;
            pref += e;
        }
        answer += 2 * half;
    }
    /*
    for (int i = 0; i < newc; ++i) {
        cerr << "\t\tcolor " << i + 1 << ":" << endl;
        for (int j : vertex[i]) {
            cerr << j + 1 << " ";
        }
        cerr << endl;
    }
    for (int i = 0; i < n; ++i) {
        cerr << "vertex " << i + 1 << endl;
        for (auto e : bycol[i]) {
            cerr << e.x + 1 << " " << e.y << endl;
        }
    }
    */
    cout << answer << endl;
    return 0;
}

/**
9 12
1 2
2 3
3 1
1 4
4 5
5 1
2 6
6 7
7 2
3 8
8 9
9 3

7 10
1 8
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
**/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48888 KB Output is correct
2 Correct 26 ms 48896 KB Output is correct
3 Correct 26 ms 48896 KB Output is correct
4 Correct 26 ms 48896 KB Output is correct
5 Correct 25 ms 48896 KB Output is correct
6 Correct 26 ms 48896 KB Output is correct
7 Incorrect 26 ms 48896 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 245 ms 90572 KB Output is correct
2 Correct 249 ms 90644 KB Output is correct
3 Correct 299 ms 98412 KB Output is correct
4 Correct 277 ms 94564 KB Output is correct
5 Correct 282 ms 92712 KB Output is correct
6 Correct 363 ms 98204 KB Output is correct
7 Correct 317 ms 98108 KB Output is correct
8 Correct 311 ms 98928 KB Output is correct
9 Correct 311 ms 97288 KB Output is correct
10 Correct 354 ms 95552 KB Output is correct
11 Correct 251 ms 89336 KB Output is correct
12 Correct 271 ms 88952 KB Output is correct
13 Correct 254 ms 87288 KB Output is correct
14 Correct 243 ms 86776 KB Output is correct
15 Correct 179 ms 82040 KB Output is correct
16 Correct 181 ms 81528 KB Output is correct
17 Correct 39 ms 60024 KB Output is correct
18 Correct 40 ms 60024 KB Output is correct
19 Correct 39 ms 59896 KB Output is correct
20 Correct 38 ms 59896 KB Output is correct
21 Correct 38 ms 59776 KB Output is correct
22 Correct 37 ms 59768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49536 KB Output is correct
2 Correct 27 ms 49536 KB Output is correct
3 Correct 30 ms 49536 KB Output is correct
4 Correct 28 ms 49536 KB Output is correct
5 Correct 28 ms 49528 KB Output is correct
6 Correct 29 ms 49536 KB Output is correct
7 Correct 28 ms 49536 KB Output is correct
8 Correct 28 ms 49536 KB Output is correct
9 Correct 28 ms 49536 KB Output is correct
10 Correct 29 ms 49528 KB Output is correct
11 Correct 28 ms 49536 KB Output is correct
12 Correct 29 ms 49504 KB Output is correct
13 Correct 29 ms 49528 KB Output is correct
14 Correct 28 ms 49408 KB Output is correct
15 Correct 28 ms 49408 KB Output is correct
16 Correct 31 ms 49400 KB Output is correct
17 Correct 37 ms 49528 KB Output is correct
18 Correct 31 ms 49536 KB Output is correct
19 Correct 31 ms 49528 KB Output is correct
20 Correct 29 ms 49536 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 107000 KB Output is correct
2 Correct 376 ms 108152 KB Output is correct
3 Correct 363 ms 108152 KB Output is correct
4 Correct 360 ms 108152 KB Output is correct
5 Correct 358 ms 108156 KB Output is correct
6 Correct 401 ms 112632 KB Output is correct
7 Correct 417 ms 111352 KB Output is correct
8 Correct 385 ms 110456 KB Output is correct
9 Correct 376 ms 109560 KB Output is correct
10 Correct 374 ms 108152 KB Output is correct
11 Correct 363 ms 108152 KB Output is correct
12 Correct 363 ms 108152 KB Output is correct
13 Correct 353 ms 108152 KB Output is correct
14 Correct 326 ms 103544 KB Output is correct
15 Correct 292 ms 98808 KB Output is correct
16 Correct 185 ms 84600 KB Output is correct
17 Execution timed out 1099 ms 83308 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49536 KB Output is correct
2 Correct 30 ms 49536 KB Output is correct
3 Incorrect 28 ms 49408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 107000 KB Output is correct
2 Correct 379 ms 108024 KB Output is correct
3 Incorrect 376 ms 104696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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