oj.uz

Submission #260965

# Submission time Handle Problem Language Result Execution time Memory
260965 2020-08-11T08:47:52 Z emanIaicepsa Duathlon (APIO18_duathlon) C++14
71 / 100
 498 ms 25464 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

const int mxn = 100005;
ll C(ll x){
    return (x)*(x-1)*(x-2)/6*2;
}

ll P(ll x){
    return C(x)*3;
}

ll n,m;
vi E[mxn], E2[mxn];
ll siz[mxn], ans=0, l[mxn], d[mxn], bcc[mxn], bcc_siz[mxn], dfn, bccid, vis[mxn], rt[mxn], siznd[mxn];
stack<int> s;

void dfs(int x,int p){
    l[x] = d[x] = ++dfn;
    siznd[x] = 1;
    s.push(x);
    for(auto i:E[x]){
        if(i==p) continue;
        if(!d[i]){
            dfs(i,x);
            siznd[x] += siznd[i];
            l[x] = min(l[x],l[i]);
        }
        else{
            l[x] = min(l[x],d[i]);
        }
    }
    if(l[x] == d[x]){
        bccid++;
        for(int i;i!=x;){
            i = s.top(); s.pop();
            bcc[i] = bccid;
        }
    }
}

void bcc_dfs(int x,int p,int anc){
    rt[x] = anc;
    siz[x] = bcc_siz[x];
    vis[x] = 1;
    for(auto i:E2[x]){
        if(i==p) continue;
        bcc_dfs(i,x,anc);
        siz[x] += siz[i];
    }
}

void bcc_dfs2(int x,int p,int anc){
    vis[x] = 1;
    for(auto i:E2[x]){
        if(i==p) continue;
        bcc_dfs2(i,x,anc);
        ans += siz[i] * (siz[anc] - siz[i] - bcc_siz[x]) * bcc_siz[x];
    }
    ans += (siz[x]-bcc_siz[x]) * (siz[anc]-siz[x]) * bcc_siz[x];
}

void dfs3(int x,int p,int anc){
    vis[x] = 1;
    ll allsiz = 0;
    vi tmp;
    for(auto i:E[x]){
        if(i==p || vis[i]) continue;
        dfs3(i,x,anc);
        if(bcc[i] != bcc[x]){
            allsiz += siznd[i];
            tmp.pb(siznd[i]);
        }
        //ans -= siznd[i] * (siznd[x] - siznd[i] - 1) * (bcc_siz[bcc[x]] - 1);
    }
    if(bcc[p] != bcc[x]){
        allsiz += siznd[anc] - siznd[x];
        tmp.pb(siznd[anc] - siznd[x]);
    }

    for(auto i:tmp){
        ans -= (i) * (allsiz-i) * (bcc_siz[bcc[x]] - 1);
    }

}

ll ok[55];
void DFS(int x,int y){
    if(x==y){
        for(int i=1;i<=n;i++) if(vis[i]) ok[i] = 1;
        return;
    }
    vis[x] = 1;
    for(auto i:E[x]){
        if(!vis[i])DFS(i,y);
    }
    vis[x] = 0;
}

void brute(int x,int y){
    for(int i=1;i<=n;i++) vis[i] = 0, ok[i] = 0;
    DFS(x,y);
    //dbg(x, y);
    for(int i=1;i<=n;i++) if(ok[i]&&i!=x&&i!=y) ans++;
    cout<<'\n';
}


signed main(){
	IOS;
    cin>>n>>m;
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        E[a].pb(b);
        E[b].pb(a);
    }

    if(n<=10){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                brute(i,j);
            }
        }
        cout<<ans<<'\n';
        return 0;
    }

    for(int i=1;i<=n;i++) if(!d[i]) dfs(i,0);

    for(int i=1;i<=n;i++){
        //dbg(i, bcc[i]);
        bcc_siz[bcc[i]]++;
        for(auto j:E[i]){
            if(bcc[i] == bcc[j]) continue;
            E2[bcc[i]].pb(bcc[j]);
            E2[bcc[j]].pb(bcc[i]);
        }
    }

    for(int i=1;i<=bccid;i++){
        sort(all(E2[i]));
        E2[i].resize(unique(all(E2[i]))-E2[i].begin());
    }

    for(int i=1;i<=bccid;i++){
        if(!vis[i]){
            bcc_dfs(i,0,i);
        }
    }
//    for(int i=1;i<=bccid;i++){
//        dbg(i, siz[i]);
//    }
    mem(vis,0);
    for(int i=1;i<=bccid;i++){
        if(bcc_siz[i]>=3){
            ll x = bcc_siz[i];
            ans += P(x);
            ans += (x-1) * (x-1) * (siz[rt[i]] - x) * 2;
        }
        if(!vis[i]){
            bcc_dfs2(i,0,i);
        }
    }
    //dbg(ans);
    mem(vis,0);
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs3(i,0,i);
    }
    //dbg(ans);

    cout<<ans<<'\n';

}
/*
3 3
1 2
2 3
3 1

4 4
1 2
2 3
3 4
2 4

5 4
1 2
2 3
1 3
4 5

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 28 ms 5376 KB Output is correct
10 Correct 498 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 4 ms 4992 KB Output is correct
18 Correct 4 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 3 ms 4992 KB Output is correct
23 Correct 4 ms 5120 KB Output is correct
24 Correct 3 ms 4992 KB Output is correct
25 Correct 3 ms 4992 KB Output is correct
26 Correct 3 ms 4992 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 3 ms 4992 KB Output is correct
29 Correct 4 ms 4992 KB Output is correct
30 Correct 4 ms 4992 KB Output is correct
31 Correct 3 ms 4992 KB Output is correct
32 Correct 4 ms 4992 KB Output is correct
33 Correct 4 ms 4992 KB Output is correct
34 Correct 3 ms 4992 KB Output is correct
35 Correct 3 ms 4992 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 28 ms 5376 KB Output is correct
10 Correct 498 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 4 ms 4992 KB Output is correct
18 Correct 4 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 3 ms 4992 KB Output is correct
23 Correct 4 ms 5120 KB Output is correct
24 Correct 3 ms 4992 KB Output is correct
25 Correct 3 ms 4992 KB Output is correct
26 Correct 3 ms 4992 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 3 ms 4992 KB Output is correct
29 Correct 4 ms 4992 KB Output is correct
30 Correct 4 ms 4992 KB Output is correct
31 Correct 3 ms 4992 KB Output is correct
32 Correct 4 ms 4992 KB Output is correct
33 Correct 4 ms 4992 KB Output is correct
34 Correct 3 ms 4992 KB Output is correct
35 Correct 3 ms 4992 KB Output is correct
36 Correct 4 ms 5888 KB Output is correct
37 Correct 4 ms 5888 KB Output is correct
38 Incorrect 4 ms 5888 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23364 KB Output is correct
2 Correct 127 ms 23492 KB Output is correct
3 Correct 133 ms 20324 KB Output is correct
4 Correct 125 ms 21624 KB Output is correct
5 Correct 123 ms 17520 KB Output is correct
6 Correct 160 ms 19576 KB Output is correct
7 Correct 151 ms 17528 KB Output is correct
8 Correct 159 ms 18424 KB Output is correct
9 Correct 144 ms 16504 KB Output is correct
10 Correct 137 ms 16888 KB Output is correct
11 Correct 133 ms 15224 KB Output is correct
12 Correct 117 ms 15224 KB Output is correct
13 Correct 109 ms 15356 KB Output is correct
14 Correct 106 ms 15224 KB Output is correct
15 Correct 91 ms 15352 KB Output is correct
16 Correct 104 ms 14948 KB Output is correct
17 Correct 14 ms 11264 KB Output is correct
18 Correct 14 ms 11264 KB Output is correct
19 Correct 13 ms 11264 KB Output is correct
20 Correct 14 ms 11264 KB Output is correct
21 Correct 14 ms 11392 KB Output is correct
22 Correct 16 ms 11264 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6016 KB Output is correct
2 Correct 4 ms 6016 KB Output is correct
3 Correct 4 ms 6016 KB Output is correct
4 Correct 5 ms 6016 KB Output is correct
5 Correct 4 ms 6016 KB Output is correct
6 Correct 4 ms 6016 KB Output is correct
7 Correct 5 ms 6016 KB Output is correct
8 Correct 4 ms 6016 KB Output is correct
9 Correct 4 ms 6016 KB Output is correct
10 Correct 4 ms 6016 KB Output is correct
11 Correct 5 ms 6016 KB Output is correct
12 Correct 5 ms 6016 KB Output is correct
13 Correct 4 ms 6016 KB Output is correct
14 Correct 6 ms 6016 KB Output is correct
15 Correct 4 ms 6016 KB Output is correct
16 Correct 5 ms 5888 KB Output is correct
17 Correct 5 ms 6016 KB Output is correct
18 Correct 6 ms 6016 KB Output is correct
19 Correct 5 ms 6016 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 169 ms 18552 KB Output is correct
2 Correct 166 ms 18424 KB Output is correct
3 Correct 147 ms 18424 KB Output is correct
4 Correct 176 ms 18424 KB Output is correct
5 Correct 150 ms 18356 KB Output is correct
6 Correct 180 ms 25464 KB Output is correct
7 Correct 172 ms 22136 KB Output is correct
8 Correct 166 ms 21112 KB Output is correct
9 Correct 163 ms 20216 KB Output is correct
10 Correct 151 ms 18424 KB Output is correct
11 Correct 167 ms 18552 KB Output is correct
12 Correct 169 ms 18376 KB Output is correct
13 Correct 170 ms 18424 KB Output is correct
14 Correct 196 ms 18168 KB Output is correct
15 Correct 163 ms 17656 KB Output is correct
16 Correct 99 ms 16120 KB Output is correct
17 Correct 126 ms 19688 KB Output is correct
18 Correct 123 ms 19436 KB Output is correct
19 Correct 140 ms 19428 KB Output is correct
20 Correct 142 ms 19296 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6016 KB Output is correct
2 Correct 5 ms 6016 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 5 ms 5888 KB Output is correct
5 Correct 4 ms 5888 KB Output is correct
6 Correct 4 ms 5888 KB Output is correct
7 Correct 4 ms 5888 KB Output is correct
8 Correct 4 ms 5888 KB Output is correct
9 Correct 4 ms 5888 KB Output is correct
10 Correct 4 ms 5888 KB Output is correct
11 Correct 4 ms 5888 KB Output is correct
12 Correct 4 ms 6016 KB Output is correct
13 Correct 5 ms 6016 KB Output is correct
14 Correct 4 ms 6016 KB Output is correct
15 Correct 5 ms 6016 KB Output is correct
16 Correct 4 ms 5888 KB Output is correct
17 Correct 4 ms 5888 KB Output is correct
18 Correct 4 ms 5888 KB Output is correct
19 Correct 4 ms 5888 KB Output is correct
20 Correct 4 ms 5888 KB Output is correct
21 Correct 4 ms 6016 KB Output is correct
22 Correct 6 ms 6016 KB Output is correct
23 Correct 5 ms 5888 KB Output is correct
24 Correct 4 ms 5888 KB Output is correct
25 Correct 4 ms 5888 KB Output is correct
26 Correct 4 ms 5888 KB Output is correct
27 Correct 4 ms 5888 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 18316 KB Output is correct
2 Correct 174 ms 18168 KB Output is correct
3 Correct 150 ms 16296 KB Output is correct
4 Correct 133 ms 14584 KB Output is correct
5 Correct 134 ms 13308 KB Output is correct
6 Correct 97 ms 12920 KB Output is correct
7 Correct 116 ms 12744 KB Output is correct
8 Correct 86 ms 12536 KB Output is correct
9 Correct 95 ms 12408 KB Output is correct
10 Correct 89 ms 12420 KB Output is correct
11 Correct 84 ms 12280 KB Output is correct
12 Correct 90 ms 12408 KB Output is correct
13 Correct 85 ms 12536 KB Output is correct
14 Correct 85 ms 15224 KB Output is correct
15 Correct 149 ms 20472 KB Output is correct
16 Correct 155 ms 19064 KB Output is correct
17 Correct 136 ms 19196 KB Output is correct
18 Correct 133 ms 17912 KB Output is correct
19 Correct 117 ms 14584 KB Output is correct
20 Correct 120 ms 14708 KB Output is correct
21 Correct 139 ms 14600 KB Output is correct
22 Correct 123 ms 14328 KB Output is correct
23 Correct 108 ms 13944 KB Output is correct
24 Correct 127 ms 16828 KB Output is correct
25 Correct 133 ms 16808 KB Output is correct
26 Correct 123 ms 15728 KB Output is correct
27 Correct 129 ms 15608 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 28 ms 5376 KB Output is correct
10 Correct 498 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 4 ms 4992 KB Output is correct
18 Correct 4 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 3 ms 4992 KB Output is correct
23 Correct 4 ms 5120 KB Output is correct
24 Correct 3 ms 4992 KB Output is correct
25 Correct 3 ms 4992 KB Output is correct
26 Correct 3 ms 4992 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 3 ms 4992 KB Output is correct
29 Correct 4 ms 4992 KB Output is correct
30 Correct 4 ms 4992 KB Output is correct
31 Correct 3 ms 4992 KB Output is correct
32 Correct 4 ms 4992 KB Output is correct
33 Correct 4 ms 4992 KB Output is correct
34 Correct 3 ms 4992 KB Output is correct
35 Correct 3 ms 4992 KB Output is correct
36 Correct 4 ms 5888 KB Output is correct
37 Correct 4 ms 5888 KB Output is correct
38 Incorrect 4 ms 5888 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 28 ms 5376 KB Output is correct
10 Correct 498 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 4 ms 4992 KB Output is correct
18 Correct 4 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 3 ms 4992 KB Output is correct
23 Correct 4 ms 5120 KB Output is correct
24 Correct 3 ms 4992 KB Output is correct
25 Correct 3 ms 4992 KB Output is correct
26 Correct 3 ms 4992 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 3 ms 4992 KB Output is correct
29 Correct 4 ms 4992 KB Output is correct
30 Correct 4 ms 4992 KB Output is correct
31 Correct 3 ms 4992 KB Output is correct
32 Correct 4 ms 4992 KB Output is correct
33 Correct 4 ms 4992 KB Output is correct
34 Correct 3 ms 4992 KB Output is correct
35 Correct 3 ms 4992 KB Output is correct
36 Correct 4 ms 5888 KB Output is correct
37 Correct 4 ms 5888 KB Output is correct
38 Incorrect 4 ms 5888 KB Output isn't correct
39 Halted 0 ms 0 KB -