oj.uz

Submission #829646

# Submission time Handle Problem Language Result Execution time Memory
829646 2023-08-18T13:45:09 Z FatihSolak Duathlon (APIO18_duathlon) C++17
31 / 100
 77 ms 27376 KB 
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<int> adj[N];
vector<int> adj2[N];
vector<int> adj3[N];
int d[N];
int low[N];
vector<pair<int,int>> edges;
int totsize[N];
int val = 0;
void dfs(int v,int par){
    d[v] = d[par] + 1;
    low[v] = d[v];
    totsize[v] = 1;
    for(auto u:adj[v]){
        if(u == par)
            continue;
        if(d[u] != 0){
            low[v] = min(d[u],low[v]);
            if(d[v] < d[u]){
                adj2[v].push_back(u);
                adj2[u].push_back(v);
            }
        }
        else{
            dfs(u,v);
            totsize[v] += totsize[u];
            low[v] = min(low[v],low[u]);
            if(low[u] <= d[v]){
                adj2[v].push_back(u);
                adj2[u].push_back(v);
            }
            else{
                edges.push_back({u,v});
            }
        }
    }
}
int cnt[N];
int group[N];
int sub[N];
int n;
long long ans = 0;
void dfs2(int v){
    cnt[group[v]]++;
    for(auto u:adj2[v]){
        if(group[u])continue;
        group[u] = group[v];
        dfs2(u);
    }
}
void dfs3(int v,int par){
    sub[v] = cnt[v];
    for(auto u:adj3[v]){
        if(u == par)
            continue;
        dfs3(u,v);
        sub[v] += sub[u];
    }
    ans += 2 * (long long)cnt[v] * (cnt[v] - 1) * (val - cnt[v]);
    ans -= 2 * (long long)(cnt[v] - 1) * (val - cnt[v]);
    for(auto u:adj3[v]){
        if(u == par){
            ans += (long long)cnt[v] * (val - sub[v]) * (sub[v] - cnt[v]);
        }
        else{
            ans += (long long)cnt[v] * (val - sub[u] - cnt[v]) * (sub[u]);
        }
    }
}
void solve(){
    int m;
    cin >> n >> m;
    for(int i = 1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1;i<=n;i++){
        if(d[i] == 0)
            dfs(i,0);
    }
    for(int i = 1;i<=n;i++){
        if(group[i] == 0){
            group[i] = i;
            dfs2(i);
            ans += (long long)cnt[i] * (cnt[i]-1) * (cnt[i]-2);
        }
    }
    for(auto u:edges){
        adj3[group[u.first]].push_back(group[u.second]);
        adj3[group[u.second]].push_back(group[u.first]);
    }
    for(int i = 1;i<=n;i++){
        if(sub[i] == 0 && group[i] == i){
            val = totsize[i];
            dfs3(i,0);
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local    
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 3 ms 7376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 3 ms 7376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 26316 KB Output is correct
2 Correct 63 ms 27376 KB Output is correct
3 Correct 73 ms 22980 KB Output is correct
4 Correct 77 ms 25540 KB Output is correct
5 Correct 52 ms 21096 KB Output is correct
6 Correct 51 ms 21188 KB Output is correct
7 Correct 49 ms 19792 KB Output is correct
8 Correct 50 ms 20728 KB Output is correct
9 Correct 69 ms 18760 KB Output is correct
10 Correct 52 ms 19676 KB Output is correct
11 Correct 42 ms 17240 KB Output is correct
12 Correct 57 ms 17040 KB Output is correct
13 Correct 47 ms 16940 KB Output is correct
14 Correct 38 ms 16680 KB Output is correct
15 Correct 30 ms 15804 KB Output is correct
16 Correct 30 ms 15520 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 8 ms 9744 KB Output is correct
19 Correct 7 ms 9684 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 6 ms 9732 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17196 KB Output is correct
2 Correct 47 ms 17604 KB Output is correct
3 Correct 48 ms 17600 KB Output is correct
4 Correct 52 ms 17600 KB Output is correct
5 Correct 49 ms 17604 KB Output is correct
6 Correct 54 ms 23264 KB Output is correct
7 Correct 58 ms 21308 KB Output is correct
8 Correct 65 ms 20296 KB Output is correct
9 Correct 52 ms 19316 KB Output is correct
10 Correct 48 ms 17608 KB Output is correct
11 Correct 54 ms 17704 KB Output is correct
12 Correct 50 ms 17720 KB Output is correct
13 Correct 74 ms 17744 KB Output is correct
14 Correct 49 ms 17392 KB Output is correct
15 Correct 41 ms 17068 KB Output is correct
16 Correct 28 ms 15440 KB Output is correct
17 Correct 42 ms 18316 KB Output is correct
18 Correct 40 ms 18236 KB Output is correct
19 Correct 45 ms 18364 KB Output is correct
20 Correct 41 ms 18240 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16876 KB Output is correct
2 Correct 50 ms 16776 KB Output is correct
3 Incorrect 62 ms 18560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 3 ms 7376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 3 ms 7376 KB Output isn't correct
8 Halted 0 ms 0 KB -