oj.uz

Submission #487136

# Submission time Handle Problem Language Result Execution time Memory
487136 2021-11-14T14:46:18 Z Redhood Duathlon (APIO18_duathlon) C++14
31 / 100
 319 ms 29324 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
#define int long long
const int N = (int)1e5 + 10;
const int M = (int)2e5 + 10;
vector < pair < int , int > > edges;
vector < int > g[N], tree[N];
int fup[N], tin[N], T, used[N];
bool bridge[M];
int get(int ide, int v){
    return (edges[ide].fi == v ? edges[ide].se : edges[ide].fi);
}
void dfs(int v, int p){
    fup[v] = tin[v] = T++;
    used[v] = 1;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(!used[to]){
            dfs(to, e);
        }
        if(e != p){
            fup[v] = min(fup[v] , fup[to]);
        }
    }
    if(p != -1){
        if(fup[v] == tin[v]){
            bridge[p] = 1;
        }
    }
}
int sz[N];

void colorit(int v, int clr){
    used[v] = clr;
    sz[clr]++;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(bridge[e]){
            if(used[to] && used[to] != clr){
                tree[used[to]].pb(clr);
                tree[clr].pb(used[to]);
            }
            continue;
        }
        if(!used[to]){
            colorit(to , clr);
        }
    }
}
int h[N];

ll ans3, ans2, ans1;



int dead[N], s[N];
void sizes(int v, int p){
    s[v] = 1;
    for(auto &u : tree[v]){
        if(!dead[u] && u != p){
            sizes(u , v);
            s[v] += s[u];
        }
    }
}
int find_cen(int v , int p, int n){
    for(auto &u : tree[v]){
        if(u != p && !dead[u] && s[u] > n / 2)
            return find_cen(u, v , n);
    }
    return v;
}
void dfs1(int v, int p, int H, vector < int > &layer){
    h[v] = H;
    layer.pb(v);
    for(auto &u : tree[v]){
        if(u == p || dead[u])
            continue;
        dfs1(u , v , H + sz[v], layer);
    }
}
vector < int > now;
int cdused[N];
void decompose(int v){
    now.pb(v);
    dead[v] = 1;
    cdused[v] = 1;
    vector < vector < int > > sons;
    for(auto &u : tree[v]){
        if(!dead[u]){
            vector < int > curlayer;
            dfs1(u , -1, sz[v], curlayer);
            sons.pb(curlayer);
        }
    }
    ll sumSmH = 0, sumS = 0;


    for(int f = 0; f < sz(sons); ++f){
        for(auto &i : sons[f]){
            sumS += sz[i];
            sumSmH += 1ll * sz[i] * h[i];
        }
    }

    for(int f = 0; f < sz(sons); ++f){
        /// delete

        ll curS = 0, curSmH =0;
        for(auto &i : sons[f]){
            curS += sz[i];
            curSmH += 1ll * sz[i] * h[i];
        }


        for(auto &i : sons[f]){
            ans3 += 1ll * sz[i] * (h[i] - sz[v]) * (sumS - curS);
            ans3 += 1ll * sz[i] * (sumSmH - curSmH);

            ans3 += 1ll * sz[i] * sz[v] * (h[i] - sz[v]) * 2;
        }
    }

    for(auto &u : tree[v]){
        if(!dead[u]){
            sizes(u , -1);
            decompose(find_cen(u , -1 , s[u]));
        }
    }
}

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

    int n , m;
    cin >> n >> m;


    for(int i = 0 ; i < m; ++i){
        int u , v;
        cin >> u >> v;
        --u , --v;
        edges.pb({u , v});
        g[u].pb(i);
        g[v].pb(i);
    }

    for(int i = 0; i < n; ++i){
        if(!used[i])
        dfs(i , -1);
    }

    /// find t


    int t = 0;
    fill(used , used + N , 0);
    for(int i = 0 ; i < n; ++i){
        if(!used[i]){
            t++;
            colorit(i , t);
        }
    }

//    /// COMPS
//    for(int i = 0 ; i < n; ++i)
//        cout << used[i] << ' ';
//    cout << endl;
//    cout << " EDGES TREE\n";
//    for(int i = 1;i <= t; ++i){
//        for(auto &u : tree[i])
//            cout << i << ' ' << u << endl;
////        cout << endl;
//    }
//
//    cout << endl;


    for(int j = 1; j <= t; ++j){
        if(cdused[j])
            continue;
        now.clear();
        sizes(j , -1);
        decompose(find_cen(j , -1 , s[j]));

        /// calc ans2 and ans1




        ll ONE = 0, SEC = 0;
        for(int i : now){
            ONE += sz[i];
            SEC += (sz[i] * (sz[i] - 1));
        }

        for(int i : now){
            ans2 += 1ll * ((sz[i]-1)*(sz[i]-2) + (sz[i]-1)) * (ONE - sz[i]) * 2;
            ans1 += 1ll * (1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2));
        }

    }
//    cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
    cout << ans1 + ans2 + ans3 << endl;
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1


11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1


4 3
1 2
2 3
3 4


4 4
1 2
2 3
3 4
4 2


6 4
1 2
2 3
4 5
5 6
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5792 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5796 KB Output is correct
7 Incorrect 3 ms 5836 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 5708 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5792 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5796 KB Output is correct
7 Incorrect 3 ms 5836 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 78 ms 19900 KB Output is correct
2 Correct 100 ms 19812 KB Output is correct
3 Correct 146 ms 21196 KB Output is correct
4 Correct 118 ms 21852 KB Output is correct
5 Correct 125 ms 19624 KB Output is correct
6 Correct 207 ms 21676 KB Output is correct
7 Correct 154 ms 19832 KB Output is correct
8 Correct 168 ms 21132 KB Output is correct
9 Correct 153 ms 18700 KB Output is correct
10 Correct 178 ms 19096 KB Output is correct
11 Correct 68 ms 17020 KB Output is correct
12 Correct 90 ms 16904 KB Output is correct
13 Correct 63 ms 17052 KB Output is correct
14 Correct 86 ms 16816 KB Output is correct
15 Correct 63 ms 16624 KB Output is correct
16 Correct 51 ms 16312 KB Output is correct
17 Correct 8 ms 10880 KB Output is correct
18 Correct 8 ms 10956 KB Output is correct
19 Correct 7 ms 10828 KB Output is correct
20 Correct 7 ms 10828 KB Output is correct
21 Correct 8 ms 10828 KB Output is correct
22 Correct 11 ms 10700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 4 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 4 ms 5964 KB Output is correct
9 Correct 4 ms 5964 KB Output is correct
10 Correct 4 ms 5964 KB Output is correct
11 Correct 4 ms 5964 KB Output is correct
12 Correct 4 ms 5964 KB Output is correct
13 Correct 4 ms 5936 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 4 ms 5928 KB Output is correct
16 Correct 3 ms 5836 KB Output is correct
17 Correct 3 ms 6004 KB Output is correct
18 Correct 3 ms 5964 KB Output is correct
19 Correct 4 ms 6092 KB Output is correct
20 Correct 4 ms 6016 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 23396 KB Output is correct
2 Correct 172 ms 23216 KB Output is correct
3 Correct 231 ms 23536 KB Output is correct
4 Correct 176 ms 23492 KB Output is correct
5 Correct 177 ms 23140 KB Output is correct
6 Correct 319 ms 26384 KB Output is correct
7 Correct 308 ms 25912 KB Output is correct
8 Correct 311 ms 25356 KB Output is correct
9 Correct 271 ms 24752 KB Output is correct
10 Correct 176 ms 22136 KB Output is correct
11 Correct 178 ms 24492 KB Output is correct
12 Correct 160 ms 22452 KB Output is correct
13 Correct 179 ms 22444 KB Output is correct
14 Correct 111 ms 20944 KB Output is correct
15 Correct 88 ms 20144 KB Output is correct
16 Correct 60 ms 17608 KB Output is correct
17 Correct 75 ms 29324 KB Output is correct
18 Correct 77 ms 29236 KB Output is correct
19 Correct 75 ms 28328 KB Output is correct
20 Correct 75 ms 27412 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 23524 KB Output is correct
2 Correct 203 ms 23104 KB Output is correct
3 Incorrect 161 ms 20528 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 5708 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5792 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5796 KB Output is correct
7 Incorrect 3 ms 5836 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 5708 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5792 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5796 KB Output is correct
7 Incorrect 3 ms 5836 KB Output isn't correct
8 Halted 0 ms 0 KB -