oj.uz

Submission #252123

# Submission time Handle Problem Language Result Execution time Memory
252123 2020-07-24T09:20:17 Z Mlxa Duathlon (APIO18_duathlon) C++14
0 / 100
 319 ms 112376 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];

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]) {
            for (auto e : bycol[v]) {
                if (e.x != i) {
                    oth.push_back(e.y);
                }
            }
        }
        /*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) {
        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;
        for (auto e : oth2) {
            int small = e.x;
            int part  = e.y;
            int full  = bycon[con[i]];
            answer -= 2 * small * (full - mcs - part);
        }
        pref = 0;
        half = 0;
        for (auto e : oth2) {
            int small = e.x;
            half += pref * small;
            pref += small;
        }
        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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 60644 KB Output is correct
2 Correct 204 ms 60748 KB Output is correct
3 Correct 254 ms 62056 KB Output is correct
4 Correct 237 ms 61304 KB Output is correct
5 Correct 235 ms 58472 KB Output is correct
6 Correct 266 ms 61296 KB Output is correct
7 Correct 275 ms 60604 KB Output is correct
8 Correct 258 ms 61424 KB Output is correct
9 Correct 244 ms 59764 KB Output is correct
10 Correct 297 ms 59160 KB Output is correct
11 Runtime error 208 ms 112376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -