oj.uz

답안 #260964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260964 2020-08-11T08:46:12 Z emanIaicepsa 철인 이종 경기 (APIO18_duathlon) C++14
66 / 100
 222 ms 25448 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);
    }

}

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);
    }


    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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 5888 KB Output is correct
3 Correct 4 ms 5888 KB Output is correct
4 Correct 4 ms 5888 KB Output is correct
5 Correct 4 ms 5888 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Incorrect 4 ms 5888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 5888 KB Output is correct
3 Correct 4 ms 5888 KB Output is correct
4 Correct 4 ms 5888 KB Output is correct
5 Correct 4 ms 5888 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Incorrect 4 ms 5888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 23364 KB Output is correct
2 Correct 108 ms 24132 KB Output is correct
3 Correct 142 ms 21240 KB Output is correct
4 Correct 124 ms 22392 KB Output is correct
5 Correct 126 ms 18296 KB Output is correct
6 Correct 151 ms 20220 KB Output is correct
7 Correct 153 ms 18208 KB Output is correct
8 Correct 148 ms 19168 KB Output is correct
9 Correct 142 ms 17148 KB Output is correct
10 Correct 160 ms 17656 KB Output is correct
11 Correct 107 ms 15864 KB Output is correct
12 Correct 98 ms 15736 KB Output is correct
13 Correct 92 ms 16120 KB Output is correct
14 Correct 105 ms 15992 KB Output is correct
15 Correct 83 ms 15996 KB Output is correct
16 Correct 89 ms 15608 KB Output is correct
17 Correct 14 ms 11264 KB Output is correct
18 Correct 14 ms 11264 KB Output is correct
19 Correct 14 ms 11264 KB Output is correct
20 Correct 14 ms 11264 KB Output is correct
21 Correct 15 ms 11264 KB Output is correct
22 Correct 14 ms 11264 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6016 KB Output is correct
2 Correct 4 ms 6016 KB Output is correct
3 Correct 5 ms 6016 KB Output is correct
4 Correct 5 ms 6016 KB Output is correct
5 Correct 5 ms 6016 KB Output is correct
6 Correct 4 ms 6016 KB Output is correct
7 Correct 4 ms 6036 KB Output is correct
8 Correct 5 ms 6016 KB Output is correct
9 Correct 5 ms 6016 KB Output is correct
10 Correct 5 ms 6016 KB Output is correct
11 Correct 4 ms 6016 KB Output is correct
12 Correct 5 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 5 ms 6016 KB Output is correct
18 Correct 5 ms 6016 KB Output is correct
19 Correct 4 ms 6016 KB Output is correct
20 Correct 4 ms 6016 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 18348 KB Output is correct
2 Correct 177 ms 18552 KB Output is correct
3 Correct 172 ms 18424 KB Output is correct
4 Correct 181 ms 18424 KB Output is correct
5 Correct 182 ms 18424 KB Output is correct
6 Correct 194 ms 25448 KB Output is correct
7 Correct 182 ms 22136 KB Output is correct
8 Correct 222 ms 21240 KB Output is correct
9 Correct 210 ms 20216 KB Output is correct
10 Correct 189 ms 18424 KB Output is correct
11 Correct 199 ms 18428 KB Output is correct
12 Correct 195 ms 18424 KB Output is correct
13 Correct 183 ms 18424 KB Output is correct
14 Correct 157 ms 18040 KB Output is correct
15 Correct 139 ms 17656 KB Output is correct
16 Correct 92 ms 15992 KB Output is correct
17 Correct 120 ms 19680 KB Output is correct
18 Correct 129 ms 19428 KB Output is correct
19 Correct 126 ms 19424 KB Output is correct
20 Correct 126 ms 19296 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6016 KB Output is correct
2 Correct 5 ms 5920 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 6 ms 5888 KB Output is correct
5 Correct 5 ms 5888 KB Output is correct
6 Correct 4 ms 5888 KB Output is correct
7 Correct 5 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 5 ms 6016 KB Output is correct
13 Correct 5 ms 6016 KB Output is correct
14 Correct 4 ms 5992 KB Output is correct
15 Correct 4 ms 6016 KB Output is correct
16 Correct 5 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 5 ms 5888 KB Output is correct
20 Correct 5 ms 5888 KB Output is correct
21 Correct 5 ms 6016 KB Output is correct
22 Correct 4 ms 6016 KB Output is correct
23 Correct 4 ms 6016 KB Output is correct
24 Correct 5 ms 6144 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

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 18424 KB Output is correct
2 Correct 189 ms 18212 KB Output is correct
3 Correct 136 ms 16248 KB Output is correct
4 Correct 138 ms 15480 KB Output is correct
5 Correct 121 ms 14328 KB Output is correct
6 Correct 109 ms 13816 KB Output is correct
7 Correct 104 ms 13560 KB Output is correct
8 Correct 100 ms 13560 KB Output is correct
9 Correct 111 ms 13304 KB Output is correct
10 Correct 101 ms 13304 KB Output is correct
11 Correct 106 ms 13176 KB Output is correct
12 Correct 108 ms 13432 KB Output is correct
13 Correct 114 ms 13592 KB Output is correct
14 Correct 106 ms 16120 KB Output is correct
15 Correct 164 ms 21372 KB Output is correct
16 Correct 170 ms 20036 KB Output is correct
17 Correct 154 ms 20088 KB Output is correct
18 Correct 149 ms 18808 KB Output is correct
19 Correct 137 ms 15480 KB Output is correct
20 Correct 146 ms 15608 KB Output is correct
21 Correct 122 ms 15608 KB Output is correct
22 Correct 103 ms 15224 KB Output is correct
23 Correct 101 ms 14840 KB Output is correct
24 Correct 125 ms 17524 KB Output is correct
25 Correct 129 ms 17652 KB Output is correct
26 Correct 143 ms 16624 KB Output is correct
27 Correct 149 ms 16376 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 5888 KB Output is correct
3 Correct 4 ms 5888 KB Output is correct
4 Correct 4 ms 5888 KB Output is correct
5 Correct 4 ms 5888 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Incorrect 4 ms 5888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 5888 KB Output is correct
3 Correct 4 ms 5888 KB Output is correct
4 Correct 4 ms 5888 KB Output is correct
5 Correct 4 ms 5888 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Incorrect 4 ms 5888 KB Output isn't correct
9 Halted 0 ms 0 KB -