#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,i,ta,tb,has,besar[101010];
vector<ll> v[101010];
ll dfs1(ll aa,ll bb)
{
besar[aa]=1;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
{
if(v[aa][ii]==bb)continue;
dfs1(v[aa][ii],aa);
besar[aa]+=besar[v[aa][ii]];
}
}
ll dfs2(ll aa,ll bb)
{
ll ii,tot=0;
vector<ll> x;
x.pb(n-besar[aa]);
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
x.pb(besar[v[aa][ii]]);
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
dfs2(v[aa][ii],aa);
for(ii=0;ii<x.size();ii++)
{
// cout<<aa<<" "<<2<<" "<<x[ii]<<" "<<tot<<"\n";
has+=2LL*x[ii]*tot;
tot+=x[ii];
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>ta>>tb;
v[ta].pb(tb);
v[tb].pb(ta);
}
dfs1(1,1);
dfs2(1,1);
cout<<has<<"\n";
}
Compilation message
count_triplets.cpp: In function 'long long int dfs1(long long int, long long int)':
count_triplets.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
count_triplets.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
count_triplets.cpp: In function 'long long int dfs2(long long int, long long int)':
count_triplets.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
count_triplets.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
count_triplets.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<x.size();ii++)
~~^~~~~~~~~
count_triplets.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
956 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
956 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
1049600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
956 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
956 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
