oj.uz

Submission #1033233

# Submission time Handle Problem Language Result Execution time Memory
1033233 2024-07-24T14:40:03 Z _8_8_ Duathlon (APIO18_duathlon) C++17
31 / 100
 107 ms 43228 KB 
#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 4e5 + 21, MOD = (int)1e9+7;
 
int n,m;

vector<vector<int>> bcc(vector<vector<int>> &g,vector<int> &sz){
    vector<bool> ap(n+1,0);
    vector<int> tin(n+1,0),up(n+1,0),id(n+1,0);
    vector<int> stk;
    vector<vector<int>> comps,G;
    function <void(int,int,int&)> dfs = [&](int v,int pr,int &t){
        tin[v] = up[v] = ++t;
        stk.push_back(v);
        int cc  =0;
        for(int to:g[v]){
            if(to == pr)continue;
            if(!tin[to]){
                dfs(to,v,t);
                cc++;
                up[v] = min(up[v],up[to]);
                if(up[to] >= tin[v]){
                    if(pr != -1){
                        ap[v] = 1;
                    }
                    comps.push_back({v});
                    while(comps.back().back() != to){
                        comps.back().push_back(stk.back());
                        stk.pop_back();
                    }  
                }
            }else{
                up[v] = min(up[v],tin[to]);
            }
        }
        if(pr == -1){
            ap[v] = (cc > 1);
        }
    };
    int timer = 0;
    for(int i = 1;i <= n;i++){
        if(!tin[i]){
            dfs(i,-1,timer);
        }
    }
    function<vector<vector<int>>()> build_tree = [&]() {
        vector<vector<int>> t(1);
        int it = 0;
        sz = vector<int> (1,0);
        for(int i = 1;i <= n;i++){
            if(ap[i]){
                id[i] = ++it;
                sz.push_back(1);
                sz[id[i]] = 1;
                t.push_back({});
            }
        }
        for(auto c:comps){
            it++;
            sz.push_back(0);
            t.push_back({});
            for(auto j:c){
                if(ap[j]){
                    t[id[j]].push_back(it);
                    t[it].push_back(id[j]);
                }else{
                    id[j] = it;
                    sz[it]++;
                }
            }
        }
        return t;
    };
    return build_tree();
}
vector<vector<int>> g(N),G;
ll calc(vector<int> &S){
    ll s = 0,d = 0,t = 0;
    for(auto i:S){
        t += i *1ll * d;
        d += s * 1ll * i;
        s += i;
    }
    return t;
}
int bf_n,nn = 0;
vector<int> sz;
bool vis[N];
ll ss[N];
void prec(int v,int pr = -1){
    vis[v] = 1;
    ss[v] += sz[v];
    for(int to:G[v]){
        if(to == pr)continue;
        prec(to,v);
        ss[v] += ss[to];
    }
}
ll res = 0;
void clac(int v,int pr = -1){
    ll c = sz[v] * 1ll * (sz[v] - 1);
    res += c / 2 *1ll * (sz[v] - 2 + (int)G[v].size()); 
    res += c * 1ll * (nn - sz[v]);
    vector<ll> vals;
    for(int to:G[v]){
        if(to == pr){
            vals.push_back(nn-ss[v]);
            continue;
        }
        clac(to,v);
        vals.push_back(ss[to]);
    }
    ll D = 0,S = 0;
    for(ll i:vals){
        D += i * S;
        S += i;
        // cout << i << ' ';
    }
    // cout << '\n';
    res += D * 1ll * sz[v];
}
void test(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    G = bcc(g,sz);
    n = (int)G.size() - 1;
    for(int i = 1;i <= n;i++){
        if(!vis[i]){
            prec(i);
            nn = ss[i];
            clac(i);
        }
    }
    cout << res * 2 << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9736 KB Output is correct
2 Correct 3 ms 9868 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 3 ms 9668 KB Output is correct
5 Correct 4 ms 9708 KB Output is correct
6 Correct 5 ms 9864 KB Output is correct
7 Incorrect 3 ms 9820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9736 KB Output is correct
2 Correct 3 ms 9868 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 3 ms 9668 KB Output is correct
5 Correct 4 ms 9708 KB Output is correct
6 Correct 5 ms 9864 KB Output is correct
7 Incorrect 3 ms 9820 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 46 ms 29484 KB Output is correct
2 Correct 51 ms 30800 KB Output is correct
3 Correct 73 ms 32816 KB Output is correct
4 Correct 60 ms 31028 KB Output is correct
5 Correct 57 ms 27796 KB Output is correct
6 Correct 63 ms 31820 KB Output is correct
7 Correct 71 ms 29292 KB Output is correct
8 Correct 70 ms 30216 KB Output is correct
9 Correct 74 ms 27388 KB Output is correct
10 Correct 66 ms 26880 KB Output is correct
11 Correct 48 ms 23048 KB Output is correct
12 Correct 44 ms 23148 KB Output is correct
13 Correct 42 ms 22808 KB Output is correct
14 Correct 44 ms 22536 KB Output is correct
15 Correct 40 ms 19652 KB Output is correct
16 Correct 36 ms 19268 KB Output is correct
17 Correct 6 ms 11596 KB Output is correct
18 Correct 6 ms 11508 KB Output is correct
19 Correct 7 ms 11624 KB Output is correct
20 Correct 5 ms 11600 KB Output is correct
21 Correct 6 ms 11500 KB Output is correct
22 Correct 5 ms 11500 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10088 KB Output is correct
2 Correct 5 ms 10088 KB Output is correct
3 Correct 4 ms 10088 KB Output is correct
4 Correct 4 ms 10088 KB Output is correct
5 Correct 4 ms 10088 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 5 ms 10076 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 3 ms 10076 KB Output is correct
10 Correct 4 ms 10076 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 3 ms 10076 KB Output is correct
13 Correct 3 ms 10076 KB Output is correct
14 Correct 3 ms 10076 KB Output is correct
15 Correct 5 ms 9824 KB Output is correct
16 Correct 4 ms 9832 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9820 KB Output is correct
19 Correct 3 ms 9816 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 30724 KB Output is correct
2 Correct 77 ms 30640 KB Output is correct
3 Correct 75 ms 30640 KB Output is correct
4 Correct 76 ms 30744 KB Output is correct
5 Correct 74 ms 30828 KB Output is correct
6 Correct 107 ms 43228 KB Output is correct
7 Correct 102 ms 37172 KB Output is correct
8 Correct 99 ms 36212 KB Output is correct
9 Correct 104 ms 33088 KB Output is correct
10 Correct 79 ms 30684 KB Output is correct
11 Correct 72 ms 30764 KB Output is correct
12 Correct 77 ms 30712 KB Output is correct
13 Correct 69 ms 30696 KB Output is correct
14 Correct 72 ms 30268 KB Output is correct
15 Correct 68 ms 25556 KB Output is correct
16 Correct 44 ms 21432 KB Output is correct
17 Correct 47 ms 26868 KB Output is correct
18 Correct 51 ms 26992 KB Output is correct
19 Correct 48 ms 26744 KB Output is correct
20 Correct 54 ms 26872 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 30800 KB Output is correct
2 Correct 76 ms 30456 KB Output is correct
3 Incorrect 80 ms 29972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9736 KB Output is correct
2 Correct 3 ms 9868 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 3 ms 9668 KB Output is correct
5 Correct 4 ms 9708 KB Output is correct
6 Correct 5 ms 9864 KB Output is correct
7 Incorrect 3 ms 9820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9736 KB Output is correct
2 Correct 3 ms 9868 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 3 ms 9668 KB Output is correct
5 Correct 4 ms 9708 KB Output is correct
6 Correct 5 ms 9864 KB Output is correct
7 Incorrect 3 ms 9820 KB Output isn't correct
8 Halted 0 ms 0 KB -