oj.uz

Submission #698645

# Submission time Handle Problem Language Result Execution time Memory
698645 2023-02-14T06:42:39 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 131 ms 28540 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;
int tot;
vector<pair<int,int> > b[maxn];
int sz[maxn];
void dfs(int u,int p=-1) {
    tot++;
    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]+=(tot-sz[u]);
        }
    }
    for(auto v:b[u]) {
        if(v.second!=p) {
            szs.push_back({sz[v.second],mp[v.first]});
        }
        else {
            szs.push_back({tot-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=tot-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*(tot-s-cnt[u]);
    }
    //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]) {
            tot=0;
            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:62:9: warning: unused variable 'pc' [-Wunused-variable]
   62 |     int pc=n-sz[u];
      |         ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 25996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9876 KB Output is correct
3 Correct 5 ms 9868 KB Output is correct
4 Correct 6 ms 10000 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 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 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 6 ms 9868 KB Output is correct
15 Correct 6 ms 9788 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 6 ms 9800 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19844 KB Output is correct
2 Correct 93 ms 19948 KB Output is correct
3 Correct 99 ms 19876 KB Output is correct
4 Correct 119 ms 19880 KB Output is correct
5 Correct 104 ms 19852 KB Output is correct
6 Correct 119 ms 28540 KB Output is correct
7 Correct 114 ms 26124 KB Output is correct
8 Correct 123 ms 24388 KB Output is correct
9 Correct 123 ms 22808 KB Output is correct
10 Correct 92 ms 19860 KB Output is correct
11 Correct 90 ms 19624 KB Output is correct
12 Correct 131 ms 19548 KB Output is correct
13 Correct 100 ms 19532 KB Output is correct
14 Correct 78 ms 19316 KB Output is correct
15 Correct 87 ms 19064 KB Output is correct
16 Correct 55 ms 17348 KB Output is correct
17 Correct 67 ms 21216 KB Output is correct
18 Correct 65 ms 21184 KB Output is correct
19 Correct 64 ms 21388 KB Output is correct
20 Correct 64 ms 20944 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 19860 KB Output is correct
2 Correct 104 ms 19600 KB Output is correct
3 Incorrect 97 ms 19240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -