oj.uz

Submission #747726

# Submission time Handle Problem Language Result Execution time Memory
747726 2023-05-24T15:07:05 Z 1075508020060209tc Duathlon (APIO18_duathlon) C++14
23 / 100
 156 ms 47340 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;

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]);
}
}

int bv;
pair<int,int> dfs2(int nw,int rtsz){
pair<int,int>ret={0,0};
for(int i=0;i<tr[nw].size();i++){
    int v=tr[nw][i];
    pair<int,int>vl=dfs2(v,rtsz);
    if(vl.first){
        ret=vl;
        ans+=(sz[v]-vl.first)*2;
    }
}
if(bke[nw].size()){
    ret={sz[nw],bke[nw][0]};
    //bv=bke[nw][0];
}
if(dwe[nw].size()){
    ret={0,0};
}

if(ret.first){
    ans+=(rtsz-sz[ret.second]+1)*(dph[nw]-dph[ret.second]-1)*2;
}


//cout<<nw<<" "<<ret<<endl;
return ret;
}



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++){
        dfs1(rt[i],sz[rt[i]]);
        dfs2(rt[i],sz[rt[i]]);
    }
    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 'std::pair<long long int, long long int> dfs2(long long int, long long int)':
count_triplets.cpp:48: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]
   48 | for(int i=0;i<tr[nw].size();i++){
      |             ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:92: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]
   92 |     for(int i=0;i<rt.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 47340 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 20 ms 28504 KB Output is correct
2 Correct 20 ms 28512 KB Output is correct
3 Correct 19 ms 28480 KB Output is correct
4 Correct 18 ms 28668 KB Output is correct
5 Correct 19 ms 28572 KB Output is correct
6 Correct 18 ms 28548 KB Output is correct
7 Correct 18 ms 28628 KB Output is correct
8 Correct 16 ms 28584 KB Output is correct
9 Correct 19 ms 28512 KB Output is correct
10 Correct 15 ms 28508 KB Output is correct
11 Correct 17 ms 28516 KB Output is correct
12 Correct 18 ms 28484 KB Output is correct
13 Correct 18 ms 28524 KB Output is correct
14 Correct 19 ms 28556 KB Output is correct
15 Correct 17 ms 28500 KB Output is correct
16 Correct 18 ms 28500 KB Output is correct
17 Correct 15 ms 28500 KB Output is correct
18 Correct 18 ms 28500 KB Output is correct
19 Correct 19 ms 28496 KB Output is correct
20 Correct 14 ms 28488 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 37136 KB Output is correct
2 Correct 124 ms 37144 KB Output is correct
3 Correct 119 ms 37220 KB Output is correct
4 Correct 125 ms 37180 KB Output is correct
5 Correct 119 ms 37196 KB Output is correct
6 Correct 138 ms 42944 KB Output is correct
7 Correct 152 ms 40896 KB Output is correct
8 Correct 133 ms 39888 KB Output is correct
9 Correct 140 ms 38968 KB Output is correct
10 Correct 122 ms 37112 KB Output is correct
11 Correct 125 ms 37196 KB Output is correct
12 Correct 122 ms 37296 KB Output is correct
13 Correct 115 ms 37196 KB Output is correct
14 Correct 104 ms 36984 KB Output is correct
15 Correct 101 ms 36740 KB Output is correct
16 Correct 65 ms 35656 KB Output is correct
17 Correct 93 ms 37008 KB Output is correct
18 Correct 89 ms 36608 KB Output is correct
19 Correct 88 ms 37084 KB Output is correct
20 Correct 90 ms 36692 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28496 KB Output is correct
2 Correct 19 ms 28480 KB Output is correct
3 Incorrect 15 ms 28500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 37184 KB Output is correct
2 Correct 129 ms 37272 KB Output is correct
3 Incorrect 150 ms 38672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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