oj.uz

Submission #698633

# Submission time Handle Problem Language Result Execution time Memory
698633 2023-02-14T06:22:48 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 115 ms 27968 KB 
#include<bits/stdc++.h>
#define maxn 200500
using namespace std;
int n,m;
vector<int> g[maxn];
bool vis[maxn];
int disc[maxn];
int low[maxn];
bool br[maxn];
int par[maxn];
int cnt[maxn];
int ct=0;
vector<pair<int,int> > b[maxn];
int sz[maxn];
void dfs(int u,int p=-1) {
    vis[u]=true;
    disc[u]=low[u]=ct++;
    sz[u]=1;
    for(auto v:g[u]) {
        if(!vis[v]) {
            dfs(v,u);
            sz[u]+=sz[v];
            par[v]=u;
            low[u]=min(low[u],low[v]);
            if(low[v]>disc[u]) {
                br[v]=true;
            }
        }
        else {
            if(v!=p) low[u]=min(low[u],disc[v]);
        }
    }
}
void dfs_2(int u,int cur=1) {
    vis[u]=true;
    if(br[u]) cur=u;
    for(auto v:g[u]) {
        if(!vis[v]) {
            if(br[v]) {
                b[cur].push_back({u,v});
                b[v].push_back({v,cur});
            }
            dfs_2(v,cur);
        }
    }
}
void dfs_3(int u,int p=-1) {
    cnt[u]=sz[u];
    for(auto v:b[u]) {
        if(v.second!=p) {
            cnt[u]-=sz[v.second];
            dfs_3(v.second,u);
        }
    }
}
long long ans=0;
int mp[maxn];
void dfs_4(int u,int p=-1) {
    int pc=n-sz[u];
    vector<pair<int,int> > szs;
    for(auto v:b[u]) {
        if(v.second!=p) {
            mp[v.first]+=sz[v.second];
        }
        else {
            mp[v.first]+=(n-sz[u]);
        }
    }
    for(auto v:b[u]) {
        if(v.second!=p) {
            szs.push_back({sz[v.second],mp[v.first]});
        }
        else {
            szs.push_back({n-sz[u],mp[v.first]});
        }
    }
    for(auto v:b[u]) {
        mp[v.first]=0;
    }
    ans = ans+1ll*cnt[u]*(cnt[u]-1)*(cnt[u]-2);
    //cout<<u<<" "<<ans<<endl;
    for(auto c:szs) {
        //cout<<"\t"<<c.first<<" "<<c.second<<endl;
        int s=c.first;
        int a=n-c.second-cnt[u];
        if(cnt[u]>=2) {
            ans=ans+2ll*(cnt[u]-1)*(cnt[u]-2)*s;
            ans=ans+2ll*(cnt[u]-1)*s;
        }
        //cout<<u<<" "<<ans<<endl;
        ans=ans+1ll*(cnt[u]-1)*s*a;
        ans=ans+1ll*s*(n-s-cnt[u]);
        //cout<<u<<" "<<ans<<endl;
    }
    //cout<<u<<" "<<ans<<endl;
    for(auto v:b[u]) {
        if(v.second!=p) dfs_4(v.second,u);
    }
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=n;i++) vis[i]=false;
    dfs_2(1);
    dfs_3(1);
    dfs_4(1);
    printf("%lld",ans);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs_4(int, int)':
count_triplets.cpp:59:9: warning: unused variable 'pc' [-Wunused-variable]
   59 |     int pc=n-sz[u];
      |         ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 25540 KB Output is correct
2 Correct 72 ms 26092 KB Output is correct
3 Incorrect 85 ms 20640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9868 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9872 KB Output is correct
4 Correct 7 ms 9868 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 6 ms 9868 KB Output is correct
10 Incorrect 6 ms 9748 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19392 KB Output is correct
2 Correct 111 ms 19288 KB Output is correct
3 Correct 100 ms 19404 KB Output is correct
4 Correct 93 ms 19284 KB Output is correct
5 Correct 104 ms 19404 KB Output is correct
6 Correct 109 ms 27968 KB Output is correct
7 Correct 115 ms 25488 KB Output is correct
8 Correct 109 ms 23896 KB Output is correct
9 Correct 107 ms 22348 KB Output is correct
10 Incorrect 69 ms 17676 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 5 ms 9872 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9844 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 5 ms 9776 KB Output is correct
11 Correct 5 ms 9748 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Incorrect 5 ms 9812 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19312 KB Output is correct
2 Correct 89 ms 19148 KB Output is correct
3 Correct 95 ms 18512 KB Output is correct
4 Correct 82 ms 18368 KB Output is correct
5 Correct 75 ms 17604 KB Output is correct
6 Correct 84 ms 17228 KB Output is correct
7 Correct 72 ms 17100 KB Output is correct
8 Correct 66 ms 16928 KB Output is correct
9 Correct 61 ms 16936 KB Output is correct
10 Correct 69 ms 16872 KB Output is correct
11 Correct 89 ms 16752 KB Output is correct
12 Correct 66 ms 17024 KB Output is correct
13 Correct 69 ms 17036 KB Output is correct
14 Correct 79 ms 18900 KB Output is correct
15 Correct 108 ms 24628 KB Output is correct
16 Correct 104 ms 23048 KB Output is correct
17 Correct 101 ms 23560 KB Output is correct
18 Correct 97 ms 22068 KB Output is correct
19 Incorrect 78 ms 18324 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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