oj.uz

Submission #946099

# Submission time Handle Problem Language Result Execution time Memory
946099 2024-03-14T10:14:26 Z sysia Duathlon (APIO18_duathlon) C++17
31 / 100
 97 ms 30404 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct DSU{
    vector<int>rep, sz;
    
    DSU(int n){
        rep.assign(n+1, 0);
        iota(rep.begin(), rep.end(), 0);
        sz.assign(n+1, 1);
    }

    int f(int a){
        return a == rep[a] ? a : rep[a] = f(rep[a]);
    }

    void u(int a, int b){
        a = f(a); b = f(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        rep[b] = a;
    }
};

void solve(){
    int n, m; cin >> n >> m;//nikt nie powiedzial ze graf jest spojny xd
    vector<vector<T>>g(n+1);
    vector<T>edges;
    vector<int>skip(m);
    for (int i = 0; i<m; i++){
        int a, b; cin >> a >> b;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
        edges.emplace_back(a, b);
    }
    vector<int>low(n+1), pre(n+1);
    int tt = 0;
    vector<bool>vis(n+1);
    function<void(int, int)>dfs = [&](int v, int pa){
        pre[v] = ++tt;
        low[v] = pre[v];
        vis[v] = 1;
        for (auto [x, i]: g[v]){
            if (x == pa) continue;
            if (vis[x]){
                low[v] = min(low[v], pre[x]);
            } else {
                // debug(v, x);
                dfs(x, v);
                low[v] = min(low[v], low[x]);
                // debug(v, pre[v], low[x]);
                if (pre[v] < low[x]){
                    debug(x, v, i);
                    skip[i] = 1;
                }
            }
        }
    };
    for (int i = 1; i<=n; i++){
        if (!vis[i]){
            dfs(i, i);
        }
    }
    DSU dsu(n+1);
    for (int i = 0; i<m; i++){
        if (!skip[i]){
            dsu.u(edges[i].first, edges[i].second);
        }
    }
    vector<vector<int>>G(n+1);
    vector<int>sz(n+1);
    for (int i = 0; i<m; i++){
        if (!skip[i]) continue;
        //most
        auto [a, b] = edges[i];
        a = dsu.f(a);b = dsu.f(b);
        debug(a, b);
        if (a != b){
            G[a].emplace_back(b);
            G[b].emplace_back(a);
        }
        // dsu.u(a, b);
    }
    vis.assign(n+1, 0);
    function<void(int, int)>subsz = [&](int v, int pa){
        sz[v] = dsu.sz[dsu.f(v)];
        vis[v] = 1;
        for (auto x: G[v]){
            if (x == pa) continue;
            subsz(x, v);
            sz[v] += sz[x];
        }
    };
    for (int i = 1; i<=n; i++){
        if (dsu.f(i) == i && !vis[i]){
            subsz(i, i);
        }
    }
    debug(dsu.sz);
    debug(sz);
    int ans = 0;
    vis.assign(n+1, 0);
    int all = 0;
    function<void(int, int)>dfessa = [&](int v, int pa){
        int sq = 0, s = 0;
        vis[v] = 1;
        for (auto x: G[v]){
            if (x == pa) continue;
            dfessa(x, v);
            sq += sz[x] * sz[x];
            s += sz[x];
        }
        //do rodzica
        int curr = dsu.sz[dsu.f(v)];
        sq += (all-sz[v])*(all-sz[v]);
        s = all-curr;
        debug(v, s, sq, curr);
        ans += 2 * curr * (s*s-sq)/2; //jeden znajduje sie tutaj
        ans += 2 * (curr-2) * (curr-1) * s; //dwa znajduja sie w jednej spojnej
        ans += 2 * s * (curr-1);
        ans += curr * (curr-1) * (curr-2);
    };
    for (int i = 1; i<=n;i++){
        if (dsu.f(i) == i && !vis[i]){
            all = sz[i];
            debug(i, all, ans);
            dfessa(i, i);
        }
    }
    debug(ans);
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 1 ms 604 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 73 ms 29892 KB Output is correct
2 Correct 59 ms 30404 KB Output is correct
3 Correct 79 ms 25540 KB Output is correct
4 Correct 60 ms 27840 KB Output is correct
5 Correct 63 ms 22724 KB Output is correct
6 Correct 65 ms 24516 KB Output is correct
7 Correct 82 ms 22724 KB Output is correct
8 Correct 66 ms 22912 KB Output is correct
9 Correct 68 ms 20944 KB Output is correct
10 Correct 61 ms 21444 KB Output is correct
11 Correct 59 ms 17860 KB Output is correct
12 Correct 49 ms 17908 KB Output is correct
13 Correct 44 ms 17344 KB Output is correct
14 Correct 46 ms 17100 KB Output is correct
15 Correct 32 ms 15816 KB Output is correct
16 Correct 46 ms 15820 KB Output is correct
17 Correct 8 ms 9048 KB Output is correct
18 Correct 7 ms 9048 KB Output is correct
19 Correct 6 ms 9048 KB Output is correct
20 Correct 6 ms 9048 KB Output is correct
21 Correct 6 ms 9048 KB Output is correct
22 Correct 6 ms 9052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20832 KB Output is correct
2 Correct 62 ms 21468 KB Output is correct
3 Correct 62 ms 21292 KB Output is correct
4 Correct 62 ms 21444 KB Output is correct
5 Correct 60 ms 21304 KB Output is correct
6 Correct 86 ms 29124 KB Output is correct
7 Correct 97 ms 27308 KB Output is correct
8 Correct 96 ms 25548 KB Output is correct
9 Correct 94 ms 24228 KB Output is correct
10 Correct 69 ms 21484 KB Output is correct
11 Correct 63 ms 21520 KB Output is correct
12 Correct 60 ms 21448 KB Output is correct
13 Correct 60 ms 21348 KB Output is correct
14 Correct 60 ms 20540 KB Output is correct
15 Correct 53 ms 19272 KB Output is correct
16 Correct 34 ms 16080 KB Output is correct
17 Correct 53 ms 21544 KB Output is correct
18 Correct 44 ms 21300 KB Output is correct
19 Correct 44 ms 21952 KB Output is correct
20 Correct 60 ms 21184 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 21076 KB Output is correct
2 Correct 66 ms 21188 KB Output is correct
3 Incorrect 91 ms 21552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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