oj.uz

Submission #747767

# Submission time Handle Problem Language Result Execution time Memory
747767 2023-05-24T16:18:18 Z 1075508020060209tc Duathlon (APIO18_duathlon) C++14
8 / 100
 150 ms 47264 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

int n;int m;
vector<int>e[300005];
vector<int>tr[300005];
vector<int>bke[300005];
vector<int>dwe[300005];
int sz[300005];int vis[300005];int dph[300005];int fa[300005];
int ans;
int ok;
void fdfs(int nw){
vis[nw]=1;
sz[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(vis[v]==0){
        fa[v]=nw;
        dph[v]=dph[nw]+1;
        tr[nw].push_back(v);
        fdfs(v);
        sz[nw]+=sz[v];
        continue;
    }
    if(v==fa[nw]){continue;}
    if(dph[v]<dph[nw]){
        bke[nw].push_back(v);
        dwe[v].push_back(nw);
    }
}
}


void dfs1(int nw,int rtsz){
//ans+=(rtsz-sz[nw])*(sz[nw]-1);
for(int i=0;i<tr[nw].size();i++){
    int v=tr[nw][i];
    dfs1(v,rtsz);
  //  ans+=sz[v]*(rtsz-1-sz[v]);
}
if(bke[nw].size()){ok=1;}
}





signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a;int b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    ans=0;
    vector<int>rt;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            rt.push_back(i);
            fdfs(i);
        }
    }
    for(int i=0;i<rt.size();i++){
        ok=0;
        dfs1(rt[i],sz[rt[i]]);
      //  cout<<rt[i]<<" "<<ok<<" "<<sz[rt[i]]<<" "<<ans<<"\n";
        if(ok){
            ans+=(sz[rt[i]]*(sz[rt[i]]-1)*(sz[rt[i]]-2));
        }else{
            ans+=(sz[rt[i]]*(sz[rt[i]]-1)*(sz[rt[i]]-2)/6)*2;
        }
    }






    cout<<ans<<endl;
}

Compilation message

count_triplets.cpp: In function 'void fdfs(long long int)':
count_triplets.cpp:17:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs1(long long int, long long int)':
count_triplets.cpp:38:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | for(int i=0;i<tr[nw].size();i++){
      |             ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:67:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<rt.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28432 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 15 ms 28396 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Incorrect 14 ms 28408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28432 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 15 ms 28396 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Incorrect 14 ms 28408 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 141 ms 47264 KB Output is correct
2 Correct 142 ms 47180 KB Output is correct
3 Correct 145 ms 42504 KB Output is correct
4 Correct 150 ms 46232 KB Output is correct
5 Correct 141 ms 42232 KB Output is correct
6 Correct 130 ms 42180 KB Output is correct
7 Correct 136 ms 40908 KB Output is correct
8 Correct 147 ms 41756 KB Output is correct
9 Correct 123 ms 40056 KB Output is correct
10 Correct 133 ms 40912 KB Output is correct
11 Correct 121 ms 38728 KB Output is correct
12 Correct 114 ms 38488 KB Output is correct
13 Correct 105 ms 38620 KB Output is correct
14 Correct 103 ms 38404 KB Output is correct
15 Correct 83 ms 37124 KB Output is correct
16 Correct 76 ms 37028 KB Output is correct
17 Correct 18 ms 31904 KB Output is correct
18 Correct 18 ms 31888 KB Output is correct
19 Correct 19 ms 31748 KB Output is correct
20 Correct 19 ms 31692 KB Output is correct
21 Correct 18 ms 31544 KB Output is correct
22 Correct 18 ms 31532 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28432 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 15 ms 28396 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Incorrect 14 ms 28408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28432 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 15 ms 28396 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Incorrect 14 ms 28408 KB Output isn't correct
8 Halted 0 ms 0 KB -