oj.uz

Submission #1033308

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

bool isb[N];
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++;
            isb[it] = 1;
            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]++;
                }
            }
            // cout << '\n';
        }
        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;
    }
    for(int i = 0;i < (int)vals.size();++i){
        if(isb[v]) res += vals[i] *1ll* sz[v]*1ll*((int)vals.size()-1);
    }
    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 5 ms 9820 KB Output is correct
2 Correct 4 ms 9672 KB Output is correct
3 Correct 6 ms 9768 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 4 ms 9816 KB Output is correct
6 Correct 4 ms 9632 KB Output is correct
7 Incorrect 4 ms 9816 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 9820 KB Output is correct
2 Correct 4 ms 9672 KB Output is correct
3 Correct 6 ms 9768 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 4 ms 9816 KB Output is correct
6 Correct 4 ms 9632 KB Output is correct
7 Incorrect 4 ms 9816 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 47 ms 30728 KB Output is correct
2 Correct 51 ms 30800 KB Output is correct
3 Correct 62 ms 32840 KB Output is correct
4 Correct 53 ms 31208 KB Output is correct
5 Correct 52 ms 27784 KB Output is correct
6 Correct 68 ms 31816 KB Output is correct
7 Correct 67 ms 29344 KB Output is correct
8 Correct 86 ms 30188 KB Output is correct
9 Correct 69 ms 27400 KB Output is correct
10 Correct 89 ms 27044 KB Output is correct
11 Correct 45 ms 23304 KB Output is correct
12 Correct 45 ms 23044 KB Output is correct
13 Correct 48 ms 22788 KB Output is correct
14 Correct 44 ms 22788 KB Output is correct
15 Correct 32 ms 19724 KB Output is correct
16 Correct 30 ms 19500 KB Output is correct
17 Correct 6 ms 11496 KB Output is correct
18 Correct 6 ms 11496 KB Output is correct
19 Correct 7 ms 11748 KB Output is correct
20 Correct 9 ms 11492 KB Output is correct
21 Correct 9 ms 11488 KB Output is correct
22 Correct 6 ms 11488 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 31964 KB Output is correct
2 Correct 70 ms 32152 KB Output is correct
3 Correct 98 ms 32000 KB Output is correct
4 Correct 84 ms 31960 KB Output is correct
5 Correct 68 ms 32004 KB Output is correct
6 Correct 112 ms 44616 KB Output is correct
7 Correct 81 ms 38364 KB Output is correct
8 Correct 103 ms 37504 KB Output is correct
9 Correct 115 ms 34368 KB Output is correct
10 Correct 90 ms 32004 KB Output is correct
11 Correct 97 ms 32080 KB Output is correct
12 Correct 75 ms 32004 KB Output is correct
13 Correct 104 ms 32172 KB Output is correct
14 Correct 62 ms 31592 KB Output is correct
15 Correct 75 ms 26628 KB Output is correct
16 Correct 33 ms 22288 KB Output is correct
17 Correct 44 ms 28192 KB Output is correct
18 Correct 48 ms 28336 KB Output is correct
19 Correct 75 ms 28280 KB Output is correct
20 Correct 44 ms 28164 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 31992 KB Output is correct
2 Correct 101 ms 31812 KB Output is correct
3 Incorrect 74 ms 31488 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 9820 KB Output is correct
2 Correct 4 ms 9672 KB Output is correct
3 Correct 6 ms 9768 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 4 ms 9816 KB Output is correct
6 Correct 4 ms 9632 KB Output is correct
7 Incorrect 4 ms 9816 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 9820 KB Output is correct
2 Correct 4 ms 9672 KB Output is correct
3 Correct 6 ms 9768 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 4 ms 9816 KB Output is correct
6 Correct 4 ms 9632 KB Output is correct
7 Incorrect 4 ms 9816 KB Output isn't correct
8 Halted 0 ms 0 KB -