oj.uz

Submission #974655

# Submission time Handle Problem Language Result Execution time Memory
974655 2024-05-03T15:13:18 Z efedmrlr Duathlon (APIO18_duathlon) C++17
31 / 100
 104 ms 31472 KB 
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e9 + 500;
int bcc = 1;
int tim = 0;
vector<int> tin(N, -1), low(N, 0);
vector<vector<int> > adj(N, vector<int>()), nadj(N, vector<int>());
vector<int> stck;
vector<int> sub(N, 0);
int n, m;
int cursz = 0;
lli ans = 0;
void dfs(int node, int par) {
    stck.pb(node);
    tin[node] = low[node] = tim++;
    cursz++;
    for(auto c : adj[node]) {
        if(c == par) {
            continue;
        }
        if(tin[c] != -1) {
            low[node] = min(low[node], tin[c]);
        }
        else {
            dfs(c, node);
            low[node] = min(low[node], low[c]);
            if(tin[node] <= low[c]) {
                assert(stck.size());
                // cout << "bcc: ";
                while(stck.back() != node) {
                    // cout << stck.back() << " ";
                    nadj[n + bcc].pb(stck.back());
                    nadj[stck.back()].pb(n + bcc);
                    stck.pop_back();
                }
                assert(stck.size());
                nadj[n + bcc].pb(node);
                nadj[node].pb(n + bcc);
                // cout << node << " \n";
                // stck.pop_back();
                bcc++;
            }
        }
    }
}

void dfs2(int node, int par) {
    sub[node] = (node <= n);
    for(auto c : nadj[node]) {
        if(c == par) continue;
        dfs2(c, node);
        sub[node] += sub[c];
        if(node > n) {
            ans -= 1ll * sub[c] * (sub[c] - 1) * (nadj[node].size() - 1);
        }
    }
    if(node > n) {
        //for parent
        int sbt = cursz - sub[node];
        ans -= 1ll * sbt * (sbt - 1) * (nadj[node].size() - 1);
    }

}

void solve() {
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++) {
        if(tin[i] != -1) continue;
        cursz = 0;
        dfs(i, 0);
        ans += 1ll * cursz * (cursz - 1) * (cursz - 2);
        dfs2(i, 0);
    }
    cout << ans << "\n";
}


signed main() {
    fastio();
    solve();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 5 ms 12124 KB Output is correct
5 Correct 5 ms 12124 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Incorrect 5 ms 12220 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 62 ms 29712 KB Output is correct
2 Correct 60 ms 29712 KB Output is correct
3 Correct 76 ms 27904 KB Output is correct
4 Correct 65 ms 28112 KB Output is correct
5 Correct 54 ms 25284 KB Output is correct
6 Correct 61 ms 26820 KB Output is correct
7 Correct 60 ms 24644 KB Output is correct
8 Correct 67 ms 25172 KB Output is correct
9 Correct 57 ms 23380 KB Output is correct
10 Correct 62 ms 23636 KB Output is correct
11 Correct 72 ms 21072 KB Output is correct
12 Correct 55 ms 20872 KB Output is correct
13 Correct 62 ms 20736 KB Output is correct
14 Correct 59 ms 20536 KB Output is correct
15 Correct 52 ms 19420 KB Output is correct
16 Correct 48 ms 19140 KB Output is correct
17 Correct 7 ms 12776 KB Output is correct
18 Correct 8 ms 12872 KB Output is correct
19 Correct 7 ms 12772 KB Output is correct
20 Correct 6 ms 12776 KB Output is correct
21 Correct 7 ms 12764 KB Output is correct
22 Correct 7 ms 13012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12176 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 7 ms 12124 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 7 ms 12380 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 5 ms 12376 KB Output is correct
8 Correct 7 ms 12380 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 6 ms 12124 KB Output is correct
11 Correct 5 ms 12168 KB Output is correct
12 Correct 6 ms 12120 KB Output is correct
13 Correct 6 ms 12124 KB Output is correct
14 Correct 5 ms 12124 KB Output is correct
15 Correct 7 ms 12124 KB Output is correct
16 Correct 5 ms 12124 KB Output is correct
17 Correct 5 ms 12124 KB Output is correct
18 Correct 5 ms 12124 KB Output is correct
19 Correct 5 ms 12124 KB Output is correct
20 Correct 6 ms 12124 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 22876 KB Output is correct
2 Correct 71 ms 22864 KB Output is correct
3 Correct 86 ms 22820 KB Output is correct
4 Correct 56 ms 23004 KB Output is correct
5 Correct 71 ms 22864 KB Output is correct
6 Correct 83 ms 31472 KB Output is correct
7 Correct 104 ms 28796 KB Output is correct
8 Correct 94 ms 26960 KB Output is correct
9 Correct 59 ms 25728 KB Output is correct
10 Correct 60 ms 22972 KB Output is correct
11 Correct 61 ms 22868 KB Output is correct
12 Correct 68 ms 22864 KB Output is correct
13 Correct 67 ms 23020 KB Output is correct
14 Correct 58 ms 22356 KB Output is correct
15 Correct 46 ms 21716 KB Output is correct
16 Correct 31 ms 19024 KB Output is correct
17 Correct 44 ms 23428 KB Output is correct
18 Correct 61 ms 23644 KB Output is correct
19 Correct 45 ms 23496 KB Output is correct
20 Correct 47 ms 23632 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Incorrect 6 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 22868 KB Output is correct
2 Correct 60 ms 22864 KB Output is correct
3 Incorrect 78 ms 22460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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