oj.uz

Submission #321285

# Submission time Handle Problem Language Result Execution time Memory
321285 2020-11-11T22:34:09 Z couplefire Duathlon (APIO18_duathlon) C++17
0 / 100
 168 ms 37732 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200015

int low[MAXN], tin[MAXN], curTime = 0, curComp = 0;
vector<int> tree[MAXN], children[MAXN];
bool isCut[MAXN];
vector<int> adj[MAXN];
bool visited[MAXN];
int n, m;
int nn = 0;
long long ans = 0;

void tarjan(int v, int p){
    visited[v] = 1;
    tin[v] = curTime++;
    low[v] = curTime-1;
    nn++;
    for(auto u : adj[v]){
        if(u == p) continue;
        if(visited[u]){
            low[v] = min(low[v], tin[u]);
        }
        else{
            children[v].push_back(u);
            tarjan(u, v);
            low[v] = min(low[v], low[u]);
            if(low[u] >= tin[v]){
                isCut[u] = 1;
            }
        }
    }
}

void ae(int a, int b){
    tree[a].push_back(b);
    tree[b].push_back(a);
}

void gen(int v, int b){
    if(b != 0) ae(v, b);
    for(auto u : children[v]){
        if(isCut[u]){
            curComp++;
            ae(v, curComp);
            gen(u, curComp);
        }
        else{
            gen(u, b);
        }
    }
}

int getSiz(int v, int p){
    if(v < n){
        int aa = 0;
        for(auto u : tree[v]){
            if(u == p) continue;
            aa += getSiz(u, v)-1;
        }
        return aa+1;
    }
    int bb = tree[v].size();
    int aa = 0;
    for(auto u : tree[v]){
        if(u == p) continue;
        if(tree[u].size() == 1) continue;
        aa += getSiz(u, v);
        bb--;
    }
    ans -= 1ll*bb*aa*(aa-1);
    ans += 1ll*bb*(tree[v].size()-bb)*(tree[v].size()-bb-1);
    if(bb+aa != nn){
        ans -= 1ll*(tree[v].size()-1)*(n-bb-aa+1)*(n-bb-aa);
    }
    // if(v == 10){
    //     cout << bb+aa << endl;
    // }
    return bb+aa;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i<m; i++){
        int a, b; cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    curComp = n-1;
    for(int i = 0; i<n; i++) if(!visited[i]) {
        nn = 0;
        tarjan(i, -1);
        ans += 1ll*nn*(nn-1)*(nn-2);
        gen(i, 0);
        getSiz(i, -1);
    }
    // for(int i = 0; i<n; i++) if(isCut[i]) cout << i+1 << endl;
    // for(int i = 0; i<MAXN; i++){
    //     if(tree[i].size()){
    //         cout << i+1 << endl;
    //         for(auto j : tree[i]) cout << j+1 << " ";
    //         cout << endl << endl;;
    //     }
    // }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Incorrect 10 ms 14444 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Incorrect 10 ms 14444 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 36044 KB Output is correct
2 Correct 125 ms 36060 KB Output is correct
3 Incorrect 141 ms 32992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14572 KB Output is correct
2 Correct 10 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 11 ms 14700 KB Output is correct
6 Correct 11 ms 14572 KB Output is correct
7 Correct 11 ms 14720 KB Output is correct
8 Correct 10 ms 14572 KB Output is correct
9 Correct 11 ms 14572 KB Output is correct
10 Incorrect 11 ms 14572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 26724 KB Output is correct
2 Correct 160 ms 28024 KB Output is correct
3 Correct 131 ms 27948 KB Output is correct
4 Correct 136 ms 27896 KB Output is correct
5 Correct 132 ms 28072 KB Output is correct
6 Correct 162 ms 37732 KB Output is correct
7 Correct 168 ms 34148 KB Output is correct
8 Correct 158 ms 32484 KB Output is correct
9 Correct 159 ms 31076 KB Output is correct
10 Incorrect 139 ms 27936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 26856 KB Output is correct
2 Correct 129 ms 28132 KB Output is correct
3 Incorrect 138 ms 28008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Incorrect 10 ms 14444 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14444 KB Output is correct
12 Incorrect 10 ms 14444 KB Output isn't correct
13 Halted 0 ms 0 KB -