oj.uz

Submission #747692

# Submission time Handle Problem Language Result Execution time Memory
747692 2023-05-24T13:32:31 Z 1075508020060209tc Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

int n;int m;
vector<int>e[300005];

int sz[300005];
int ans;
void dfssz(int nw,int pa){
sz[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfssz(v,nw);
    sz[nw]+=sz[v];
}
}



void dfs(int nw,int pa,int rtsz){
ans+=(rtsz-sz[nw])*(sz[nw]-1);
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfs(v,nw,rtsz);
    ans+=sz[v]*(rtsz-1-sz[v]);
}
}


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(sz[i]==0){
            dfssz(i,0);
            rt.push_back(i);
        }
    }
    for(int i=0;i<rt.size();i++){
        dfs(rt[i],0,sz[rt[i]]);
    }
    cout<<ans<<endl;
}

Compilation message

count_triplets.cpp: In function 'void dfssz(long long int, long long int)':
count_triplets.cpp:13: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]
   13 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int, long long int, long long int)':
count_triplets.cpp:25: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]
   25 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:51: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]
   51 |     for(int i=0;i<rt.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 624316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7360 KB Output is correct
3 Correct 5 ms 7388 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7420 KB Output is correct
8 Correct 4 ms 7360 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7392 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 5 ms 7380 KB Output is correct
13 Correct 4 ms 7364 KB Output is correct
14 Correct 4 ms 7360 KB Output is correct
15 Correct 5 ms 7380 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 5 ms 7360 KB Output is correct
18 Correct 6 ms 7380 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 5 ms 7380 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 13060 KB Output is correct
2 Correct 94 ms 13104 KB Output is correct
3 Correct 84 ms 12988 KB Output is correct
4 Correct 91 ms 13112 KB Output is correct
5 Correct 86 ms 13008 KB Output is correct
6 Correct 116 ms 16752 KB Output is correct
7 Correct 111 ms 15800 KB Output is correct
8 Correct 118 ms 15052 KB Output is correct
9 Correct 94 ms 14404 KB Output is correct
10 Correct 89 ms 13112 KB Output is correct
11 Correct 88 ms 12988 KB Output is correct
12 Correct 85 ms 13040 KB Output is correct
13 Correct 95 ms 13072 KB Output is correct
14 Correct 94 ms 12900 KB Output is correct
15 Correct 83 ms 12700 KB Output is correct
16 Correct 51 ms 11748 KB Output is correct
17 Correct 79 ms 13292 KB Output is correct
18 Correct 83 ms 13308 KB Output is correct
19 Correct 78 ms 13264 KB Output is correct
20 Correct 81 ms 13272 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7364 KB Output is correct
2 Correct 5 ms 7360 KB Output is correct
3 Runtime error 743 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 13048 KB Output is correct
2 Correct 100 ms 12876 KB Output is correct
3 Runtime error 697 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -