oj.uz

Submission #252136

# Submission time Handle Problem Language Result Execution time Memory
252136 2020-07-24T10:01:10 Z Mlxa Duathlon (APIO18_duathlon) C++14
8 / 100
 440 ms 107088 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;
        }
        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;

        oth.clear();
        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);
        //cerr << "###\t" << i << " " << mcs  << endl;
        int part = without[i][maxcol[i]];
        int small = without2[i][maxcol[i]];
        answer -= 2 * small * (bycon[con[i]] - mcs - part);
    }
    /*
    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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48896 KB Output is correct
2 Correct 28 ms 48896 KB Output is correct
3 Correct 28 ms 48896 KB Output is correct
4 Correct 26 ms 48896 KB Output is correct
5 Correct 26 ms 48896 KB Output is correct
6 Correct 27 ms 48896 KB Output is correct
7 Incorrect 28 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 48896 KB Output is correct
2 Correct 28 ms 48896 KB Output is correct
3 Correct 28 ms 48896 KB Output is correct
4 Correct 26 ms 48896 KB Output is correct
5 Correct 26 ms 48896 KB Output is correct
6 Correct 27 ms 48896 KB Output is correct
7 Incorrect 28 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 255 ms 90596 KB Output is correct
2 Correct 259 ms 90588 KB Output is correct
3 Correct 314 ms 98412 KB Output is correct
4 Correct 271 ms 94572 KB Output is correct
5 Correct 271 ms 92652 KB Output is correct
6 Correct 353 ms 98328 KB Output is correct
7 Correct 311 ms 98032 KB Output is correct
8 Correct 319 ms 98928 KB Output is correct
9 Correct 324 ms 97524 KB Output is correct
10 Correct 339 ms 95600 KB Output is correct
11 Correct 247 ms 89336 KB Output is correct
12 Correct 248 ms 88952 KB Output is correct
13 Correct 298 ms 87416 KB Output is correct
14 Correct 235 ms 86776 KB Output is correct
15 Correct 176 ms 82040 KB Output is correct
16 Correct 229 ms 81500 KB Output is correct
17 Correct 39 ms 60024 KB Output is correct
18 Correct 41 ms 60156 KB Output is correct
19 Correct 41 ms 60024 KB Output is correct
20 Correct 40 ms 59896 KB Output is correct
21 Correct 51 ms 59872 KB Output is correct
22 Correct 42 ms 59904 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 49536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 437 ms 107060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 49536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 440 ms 107088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48896 KB Output is correct
2 Correct 28 ms 48896 KB Output is correct
3 Correct 28 ms 48896 KB Output is correct
4 Correct 26 ms 48896 KB Output is correct
5 Correct 26 ms 48896 KB Output is correct
6 Correct 27 ms 48896 KB Output is correct
7 Incorrect 28 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 48896 KB Output is correct
2 Correct 28 ms 48896 KB Output is correct
3 Correct 28 ms 48896 KB Output is correct
4 Correct 26 ms 48896 KB Output is correct
5 Correct 26 ms 48896 KB Output is correct
6 Correct 27 ms 48896 KB Output is correct
7 Incorrect 28 ms 48896 KB Output isn't correct
8 Halted 0 ms 0 KB -