oj.uz

Submission #252130

# Submission time Handle Problem Language Result Execution time Memory
252130 2020-07-24T09:41:51 Z Mlxa Duathlon (APIO18_duathlon) C++14
0 / 100
 370 ms 106872 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;
                    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;
        for (int e : oth) {
            half += cur * pref * e;
            pref += e;
        }
        answer += 2 * half;
    }
    for (int i = 0; i < n; ++i) {
        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 32 ms 48896 KB Output is correct
2 Correct 26 ms 48896 KB Output is correct
3 Correct 35 ms 48896 KB Output is correct
4 Correct 35 ms 48896 KB Output is correct
5 Correct 25 ms 48896 KB Output is correct
6 Correct 27 ms 48896 KB Output is correct
7 Incorrect 25 ms 48888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 90536 KB Output is correct
2 Correct 249 ms 90596 KB Output is correct
3 Incorrect 340 ms 98552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 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 361 ms 106872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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