#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((int)(bi)))
#define endl '\n'
#define int long long
//mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#ifdef tolbi
#include "duathlon.h"
#endif
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((int)(bi)))
#define endl '\n'
#define int long long
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#ifdef tolbi
#include "duathlon.h"
#endif
#include <bits/stdc++.h>
using namespace std;
int solve(int n, vector<int> u, vector<int> v){
vector<vector<int>> arr(n);
for (int i = 0; i < u.size(); i++){
arr[u[i]].push_back(v[i]);
arr[v[i]].push_back(u[i]);
}
vector<int> dept(n,-1);
vector<int> stk;
vector<int> ele(n);
vector<int> sz;
vector<vector<int>> hehe;
function<int(int,int)> f;
vector<int> par(n);
f = [&](int node, int lnode)->int{
if (lnode!=-1) par[node]=lnode;
if (lnode!=-1) dept[node]=dept[lnode]+1;
int mide = dept[node];
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i]==lnode) continue;
if (dept[arr[node][i]]!=-1){
mide=min(mide,dept[arr[node][i]]);
continue;
}
mide=min(mide,f(arr[node][i],node));
}
stk.push_back(node);
if (mide==dept[node]){
sz.push_back(0);
while (stk.size()){
ele[stk.back()]=hehe.size();
stk.pop_back();
sz.back()++;
}
hehe.push_back(vector<int>());
}
return mide;
};
dept[0]=0;
f(0,-1);
for (int i = 1; i < n; i++){
if (ele[i]!=ele[par[i]]){
hehe[ele[i]].push_back(ele[par[i]]);
hehe[ele[par[i]]].push_back(ele[i]);
}
}
n=hehe.size();
swap(arr,hehe);
int ans = 0;
for (int i = 0; i < sz.size(); i++){
ans+=sz[i]*(sz[i]-1)*(sz[i]-2);
}//3 from cycle
vector<int> subsz(n);
f = [&](int node, int lnode)->int{
subsz[node]=sz[node];
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i]==lnode) continue;
f(arr[node][i],node);
subsz[node]+=subsz[arr[node][i]];
ans+=(subsz[arr[node][i]])*(sz[node])*(n-subsz[arr[node][i]]-sz[node])*2;
//2 from outside, 1 from cycle
ans+=(sz[node]-1)*(sz[node]-1)*subsz[arr[node][i]];
//2 from cycle, 1 from outside
}
ans+=(sz[node]-1)*(sz[node]-1)*(n-subsz[node]);
return 23;
};
f(0,-1);
return ans;
}
int32_t main(){
int T = 1;
int tno = 0;
while (T-(tno++)){
deci(n);deci(m);
vector<int> par(n);
iota(par.begin(), par.end(), 0);
function<int(int)> find;
find = [&](int node)->int{
if (par[node]==node) return node;
return par[node]=find(par[node]);
};
vector<pair<int,int>> edges(m);
for (int i = 0; i < m; i++){
cin>>edges[i].first>>edges[i].second;
edges[i].first--,edges[i].second--;
int u = edges[i].first;
int v = edges[i].second;
u=find(u);
v=find(v);
par[u]=v;
}
map<int,int> mp;
map<int,vector<int>> u;
map<int,vector<int>> v;
vector<int> indis(n);
for (int i = 0; i < n; i++){
indis[i]=mp[find(i)]++;
}
for (int i = 0; i < m; i++){
u[find(edges[i].first)].push_back(indis[edges[i].first]);
v[find(edges[i].second)].push_back(indis[edges[i].second]);
}
int ans = 0;
for (auto it : mp){
ans+=solve(it.second,u[it.first],v[it.first]);
}
cout<<ans<<endl;
}
}
Compilation message
count_triplets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("Bismillahirrahmanirrahim")
|
count_triplets.cpp:28: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
28 | #pragma optimize("Bismillahirrahmanirrahim")
|
count_triplets.cpp: In function 'long long int solve(long long int, std::vector<long long int>, std::vector<long long int>)':
count_triplets.cpp:59:23: 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]
59 | for (int i = 0; i < u.size(); i++){
| ~~^~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:74:27: 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]
74 | for (int i = 0; i < arr[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int solve(long long int, std::vector<long long int>, std::vector<long long int>)':
count_triplets.cpp:105:23: 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]
105 | for (int i = 0; i < sz.size(); i++){
| ~~^~~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:111:27: 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]
111 | for (int i = 0; i < arr[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
25536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
22840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
22888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
