oj.uz

Submission #710666

# Submission time Handle Problem Language Result Execution time Memory
710666 2023-03-15T14:31:44 Z Stickfish Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 1048576 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 23;
vector<int> edg[MAXN];
int depth[MAXN];
int tin[MAXN];
int fup[MAXN];
int timer = 0;
bitset<MAXN> used;

vector<int> stck;
vector<int> comps[MAXN];
vector<int> cedg[MAXN];
int csz[MAXN];
int compcnt = 0;
int rcomps[MAXN];

void dfs(int v, int rt) {
    used[v] = 1;
    tin[v] = fup[v] = timer++;
    stck.push_back(v);
    for (auto u : edg[v]) {
        if (u == rt)
            continue;
        if (used[u]) {
            fup[v] = min(fup[v], tin[u]);
            continue;
        }
        dfs(u, v);
        fup[v] = min(fup[v], fup[u]);
        if (fup[u] > tin[v]) {
            while (stck.back() != v) {
                comps[compcnt].push_back(stck.back());
                rcomps[stck.back()] = compcnt;
                stck.pop_back();
            }
            ++compcnt;
        }
    }
}

void cdfs(int v, int rt) {
    csz[v] = comps[v].size();
    for (auto u : cedg[v]) {
        if (u == rt)
            continue;
        cdfs(u, v);
        csz[v] += csz[u];
    }
}

signed main() {
    int n, m; 
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    dfs(0, 0);
    while (stck.size()) {
        comps[compcnt].push_back(stck.back());
        rcomps[stck.back()] = compcnt;
        stck.pop_back();
    }
    ++compcnt;
    for (int v = 0; v < n; ++v) {
        for (auto u : edg[v]) {
            if (rcomps[v] != rcomps[u])
                cedg[rcomps[v]].push_back(rcomps[u]);
        }
    }
    cdfs(0, 0);
    //cout << compcnt << endl;
    //for (int i = 0; i < compcnt; ++i)
        //cout << comps[i].size() << ' ';
    //cout << endl;
    //cout << endl;
    ll ans = 1ll * n * (n - 1) * (n - 2);
    for (int v = 0; v < compcnt; ++v) {
        for (auto u : cedg[v]) {
            if (csz[u] > csz[v])
                continue;
            //cout << comps[v].size() << ' ' << csz[u] << endl;
            ans -= 1ll * csz[u] * (csz[u] - 1) * comps[v].size();
            ans -= 2ll * csz[u] * (comps[v].size() - 1);
        }
        
        ans -= 1ll * (n - csz[v]) * (n - csz[v] - 1) * comps[v].size();
        ans -= 2ll * (n - csz[v]) * (comps[v].size() - 1);
        //cout << "!" << comps[v].size() << ' ' << n - csz[v] << endl;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 20848 KB Output is correct
2 Correct 105 ms 20812 KB Output is correct
3 Incorrect 92 ms 16336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 5 ms 7564 KB Output is correct
7 Correct 5 ms 7496 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Incorrect 5 ms 7380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 18772 KB Output is correct
2 Correct 131 ms 19184 KB Output is correct
3 Correct 124 ms 19176 KB Output is correct
4 Correct 130 ms 19236 KB Output is correct
5 Correct 120 ms 19276 KB Output is correct
6 Correct 142 ms 27080 KB Output is correct
7 Correct 142 ms 22088 KB Output is correct
8 Correct 137 ms 21236 KB Output is correct
9 Correct 169 ms 20492 KB Output is correct
10 Incorrect 104 ms 16340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 593 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 18980 KB Output is correct
2 Correct 148 ms 19252 KB Output is correct
3 Execution timed out 1094 ms 252856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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