oj.uz

Submission #747724

# Submission time Handle Problem Language Result Execution time Memory
747724 2023-05-24T15:03:01 Z 1075508020060209tc Duathlon (APIO18_duathlon) C++14
23 / 100
 154 ms 47180 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;
int dfs2(int nw,int rtsz){
int ret=0;
for(int i=0;i<tr[nw].size();i++){
    int v=tr[nw][i];
    int vl=dfs2(v,rtsz);
    if(vl){
        ret=vl;
        ans+=(sz[v]-vl)*2;
    }
}
if(bke[nw].size()){
    ret=sz[nw];
    bv=bke[nw][0];
}
if(dwe[nw].size()){
    ret=0;
}

if(ret){
    ans+=(rtsz-sz[bv]+1)*(dph[nw]-dph[bv]-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 '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 14 ms 28504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 47180 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 18 ms 28508 KB Output is correct
2 Correct 18 ms 28540 KB Output is correct
3 Correct 17 ms 28508 KB Output is correct
4 Correct 16 ms 28656 KB Output is correct
5 Correct 19 ms 28524 KB Output is correct
6 Correct 17 ms 28596 KB Output is correct
7 Correct 20 ms 28648 KB Output is correct
8 Correct 18 ms 28516 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 21 ms 28536 KB Output is correct
12 Correct 16 ms 28496 KB Output is correct
13 Correct 19 ms 28500 KB Output is correct
14 Correct 18 ms 28500 KB Output is correct
15 Correct 18 ms 28492 KB Output is correct
16 Correct 15 ms 28544 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 18 ms 28488 KB Output is correct
19 Correct 16 ms 28580 KB Output is correct
20 Correct 19 ms 28584 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 37232 KB Output is correct
2 Correct 122 ms 37232 KB Output is correct
3 Correct 128 ms 37196 KB Output is correct
4 Correct 125 ms 37216 KB Output is correct
5 Correct 130 ms 37196 KB Output is correct
6 Correct 153 ms 42968 KB Output is correct
7 Correct 141 ms 40904 KB Output is correct
8 Correct 139 ms 39868 KB Output is correct
9 Correct 122 ms 39056 KB Output is correct
10 Correct 123 ms 37196 KB Output is correct
11 Correct 141 ms 37572 KB Output is correct
12 Correct 145 ms 37664 KB Output is correct
13 Correct 137 ms 37580 KB Output is correct
14 Correct 121 ms 37344 KB Output is correct
15 Correct 116 ms 37208 KB Output is correct
16 Correct 71 ms 36104 KB Output is correct
17 Correct 104 ms 37436 KB Output is correct
18 Correct 98 ms 37016 KB Output is correct
19 Correct 90 ms 37360 KB Output is correct
20 Correct 95 ms 37020 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28668 KB Output is correct
2 Correct 19 ms 28508 KB Output is correct
3 Incorrect 16 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 136 ms 37152 KB Output is correct
2 Correct 132 ms 37324 KB Output is correct
3 Incorrect 154 ms 38648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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