oj.uz

Submission #698637

# Submission time Handle Problem Language Result Execution time Memory
698637 2023-02-14T06:30:37 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 115 ms 28384 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];
bool c_vis[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) {
    c_vis[u]=true;
    if(br[u]) cur=u;
    for(auto v:g[u]) {
        if(!c_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 brute() {
    for(int c=1;c<=n;c++) {
        dfs_5(c);
    }
}*/
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);
    }
    for(int u=1;u<=n;u++) {
        if(!vis[u]) {
            dfs(u);
            dfs_2(u,u);
            dfs_3(u,u);
            dfs_4(u,u);
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs_4(int, int)':
count_triplets.cpp:60:9: warning: unused variable 'pc' [-Wunused-variable]
   60 |     int pc=n-sz[u];
      |         ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         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 9688 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 5 ms 9732 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 9688 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 5 ms 9732 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 70 ms 25960 KB Output is correct
2 Correct 73 ms 26024 KB Output is correct
3 Incorrect 94 ms 24612 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 9872 KB Output is correct
2 Correct 5 ms 9872 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 5 ms 9872 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9880 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Incorrect 6 ms 9812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19756 KB Output is correct
2 Correct 90 ms 19680 KB Output is correct
3 Correct 94 ms 19736 KB Output is correct
4 Correct 94 ms 19720 KB Output is correct
5 Correct 95 ms 19788 KB Output is correct
6 Correct 115 ms 28384 KB Output is correct
7 Correct 110 ms 25772 KB Output is correct
8 Correct 109 ms 24268 KB Output is correct
9 Correct 107 ms 22628 KB Output is correct
10 Incorrect 93 ms 19712 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9828 KB Output is correct
5 Correct 6 ms 9764 KB Output is correct
6 Correct 6 ms 9784 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 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 6 ms 9872 KB Output is correct
16 Incorrect 6 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 89 ms 19864 KB Output is correct
2 Correct 92 ms 19660 KB Output is correct
3 Correct 88 ms 18480 KB Output is correct
4 Correct 88 ms 18508 KB Output is correct
5 Correct 74 ms 17604 KB Output is correct
6 Correct 68 ms 17356 KB Output is correct
7 Correct 65 ms 17196 KB Output is correct
8 Correct 61 ms 17100 KB Output is correct
9 Correct 63 ms 16972 KB Output is correct
10 Correct 72 ms 16884 KB Output is correct
11 Correct 76 ms 16856 KB Output is correct
12 Correct 59 ms 17092 KB Output is correct
13 Correct 69 ms 17076 KB Output is correct
14 Correct 75 ms 19148 KB Output is correct
15 Correct 99 ms 24748 KB Output is correct
16 Correct 99 ms 23156 KB Output is correct
17 Correct 92 ms 23604 KB Output is correct
18 Correct 96 ms 22092 KB Output is correct
19 Incorrect 86 ms 18628 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 9688 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 5 ms 9732 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 9688 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -