oj.uz

Submission #260882

# Submission time Handle Problem Language Result Execution time Memory
260882 2020-08-11T06:51:12 Z emanIaicepsa Duathlon (APIO18_duathlon) C++14
31 / 100
 173 ms 24824 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...);}

ll n,m;
vi E[100005];
ll siz[100005], ans=0;
bool vis[100005];

int pa[100005][18], dep[100005];

ll C(ll x){
    return (x)*(x-1)*(x-2)/6*2;
}

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

vector<pii> circ;

void dfs(int x,int p){
    vis[x] = 1;
    siz[x] = 1;
    dep[x] = dep[p] + 1;
    pa[x][0] = p;
    for(int i=1;i<=__lg(n);i++){
        pa[x][i] = pa[ pa[x][i-1] ][i-1];
    }
    for(auto i:E[x]){
        if(i==p) continue;
        else if(vis[i]){
            if(x<i)circ.pb(x,i);
        }
        else{
            dfs(i,x);
            siz[x] += siz[i];
        }
    }
}

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

int dis(int x,int y){
    ll ans = 0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=__lg(n),le=dep[x]-dep[y];i>=0;i--){
        if(le>=(1<<i)){
            le -= 1<<i;
            ans += 1<<i;
            x = pa[x][i];
        }
    }
    if(x==y) return ans;
    for(int i=__lg(n);i>=0;i--){
        if(pa[x][i] != pa[y][i]){
            x = pa[x][i];
            y = pa[y][i];
            ans += (1<<i)*2;
        }
    }
    return ans+2;
}

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(!vis[i]) dfs(i,0);
    mem(vis,0);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs2(i,0,i);

    for(auto i:circ){
        int d = dis(i.fi,i.se) + 1;
        ans -= C(d);
        ans += P(d);
    }

    cout<<ans<<'\n';

}
/*
3 3
1 2
2 3
3 1
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 23544 KB Output is correct
2 Correct 173 ms 24824 KB Output is correct
3 Correct 138 ms 20120 KB Output is correct
4 Correct 144 ms 22392 KB Output is correct
5 Correct 131 ms 18576 KB Output is correct
6 Correct 151 ms 18552 KB Output is correct
7 Correct 133 ms 17308 KB Output is correct
8 Correct 128 ms 18040 KB Output is correct
9 Correct 132 ms 16376 KB Output is correct
10 Correct 143 ms 17284 KB Output is correct
11 Correct 106 ms 15608 KB Output is correct
12 Correct 106 ms 15480 KB Output is correct
13 Correct 93 ms 15352 KB Output is correct
14 Correct 93 ms 15188 KB Output is correct
15 Correct 74 ms 14544 KB Output is correct
16 Correct 75 ms 14516 KB Output is correct
17 Correct 17 ms 11008 KB Output is correct
18 Correct 18 ms 11008 KB Output is correct
19 Correct 15 ms 11008 KB Output is correct
20 Correct 15 ms 11136 KB Output is correct
21 Correct 16 ms 11008 KB Output is correct
22 Correct 15 ms 11008 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14200 KB Output is correct
2 Correct 113 ms 14292 KB Output is correct
3 Correct 104 ms 14284 KB Output is correct
4 Correct 108 ms 14328 KB Output is correct
5 Correct 107 ms 14200 KB Output is correct
6 Correct 140 ms 19192 KB Output is correct
7 Correct 145 ms 17528 KB Output is correct
8 Correct 135 ms 16632 KB Output is correct
9 Correct 133 ms 15864 KB Output is correct
10 Correct 118 ms 14328 KB Output is correct
11 Correct 113 ms 14292 KB Output is correct
12 Correct 108 ms 14328 KB Output is correct
13 Correct 118 ms 14328 KB Output is correct
14 Correct 128 ms 14328 KB Output is correct
15 Correct 103 ms 14072 KB Output is correct
16 Correct 64 ms 13304 KB Output is correct
17 Correct 89 ms 14576 KB Output is correct
18 Correct 74 ms 14576 KB Output is correct
19 Correct 78 ms 14572 KB Output is correct
20 Correct 73 ms 14584 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -