oj.uz

Submission #967865

# Submission time Handle Problem Language Result Execution time Memory
967865 2024-04-23T03:18:45 Z socpite Duathlon (APIO18_duathlon) C++14
0 / 100
 130 ms 33780 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;

vector<int> g[maxn];
int sz[maxn], dp[maxn];
vector<int> blg[maxn];

int low[maxn], num[maxn];

int n, m, bcsz;
long long ans = 0;

int tdfs;
stack<int> stk;

void addedge(int a, int b){
    // cout << a << " " << b << endl;
    blg[a].push_back(b);
    blg[b].push_back(a);
}

void dfs(int x, int p){
    stk.push(x);
    low[x] = num[x] = ++tdfs;
    for(auto v:g[x]){
        if(v == p)continue;
        if(num[v])low[x] = min(low[x], num[v]);
        else {
            dfs(v, x);
            low[x] = min(low[x], low[v]);
        }
    }
    if(p){
        if(low[x] == num[p]){
            bcsz++;
            while(stk.top() != x){
                addedge(stk.top(), bcsz);
                sz[bcsz]++;
                stk.pop();
            }
            addedge(x, bcsz);
            sz[bcsz]++;
            stk.pop();
            addedge(p, bcsz);
        }
        else if(low[x] == num[x]){
            stk.pop();
            bcsz++;
            sz[bcsz] = 1;
            addedge(x, bcsz);
            addedge(p, bcsz);

        }
    }
}

long long dfs2(int x, int p){
    dp[x] = (x <= n);
    long long re = 0;
    for(auto v: blg[x]){
        if(v == p)continue;
        re += dfs2(v, x);
        dp[x] += dp[v];
        if(x <= n){
            re += 1LL*dp[v]*(n - dp[v] - 1);
        }
        else {
            re += 1LL*(blg[x].size()-2)*dp[v]*(n-dp[v]);
        }
    }
    if(x <= n){
        re += 1LL*(n - dp[x])*(dp[x] - 1);
    }
    else {
        re += 1LL*(blg[x].size()-2)*(n - dp[x])*(dp[x]);
    }
    // cout << "SUS " << x << " " << re << endl;
    return re;
}

int main() {
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bcsz = n;
    dfs(1, 0);
    cout << dfs2(1, 0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12632 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 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28684 KB Output is correct
2 Correct 82 ms 28464 KB Output is correct
3 Incorrect 65 ms 22844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12760 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12732 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Incorrect 3 ms 12636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 23588 KB Output is correct
2 Correct 79 ms 23632 KB Output is correct
3 Correct 82 ms 23636 KB Output is correct
4 Correct 92 ms 23652 KB Output is correct
5 Correct 87 ms 23748 KB Output is correct
6 Correct 112 ms 33780 KB Output is correct
7 Correct 90 ms 30288 KB Output is correct
8 Correct 109 ms 28876 KB Output is correct
9 Correct 87 ms 26964 KB Output is correct
10 Incorrect 67 ms 20796 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12792 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 3 ms 12716 KB Output is correct
9 Correct 4 ms 12636 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 3 ms 12772 KB Output is correct
12 Correct 3 ms 12888 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12800 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Incorrect 4 ms 12636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 23804 KB Output is correct
2 Correct 86 ms 23636 KB Output is correct
3 Correct 93 ms 23120 KB Output is correct
4 Correct 100 ms 22500 KB Output is correct
5 Correct 105 ms 21788 KB Output is correct
6 Correct 97 ms 21692 KB Output is correct
7 Correct 77 ms 21400 KB Output is correct
8 Correct 70 ms 21284 KB Output is correct
9 Correct 75 ms 21328 KB Output is correct
10 Correct 70 ms 21140 KB Output is correct
11 Correct 110 ms 21072 KB Output is correct
12 Correct 66 ms 21076 KB Output is correct
13 Correct 74 ms 21076 KB Output is correct
14 Correct 77 ms 22972 KB Output is correct
15 Correct 98 ms 30156 KB Output is correct
16 Correct 97 ms 27808 KB Output is correct
17 Correct 93 ms 28752 KB Output is correct
18 Correct 130 ms 26908 KB Output is correct
19 Incorrect 83 ms 22240 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12632 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 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -