#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
//Union-Find木(ランク有り)
struct UnionFind{
private:
vector<int> parent;
vector<int> size;
public:
void init(int N){ //初期化する O(N)
parent.clear();
size.clear();
for(int i=0; i<N; i++) parent.push_back(i);
for(int i=0; i<N; i++) size.push_back(1);
}
int root(int a){ //親を返す O(log N)
if(parent[a] == a) return a;
return parent[a] = root(parent[a]);
}
void unite(int a, int b){ //木を併合する O(log N)
int rootA = root(a);
int rootB = root(b);
if(rootA == rootB) return;
if(size[rootA] < size[rootB]){
parent[rootA] = rootB;
size[rootB] += size[rootA];
size[rootA] = 0;
}
else{
parent[rootB] = rootA;
size[rootA] += size[rootB];
size[rootB] = 0;
}
}
bool same(int a, int b){ //属する木が同じかを返す O(log N)
return root(a) == root(b);
}
};
LL N, M;
vector<int> edge[100000];
vector<bool> canUse[100000];
int sz[100000];
int pre[100000]={}, low[100000];
int c = 0;
vector<pair<int, int>> bridge;
int dfs(int now, int par, int idx){
if(pre[now] != 0) return pre[now];
pre[now] = c; c++;
low[now] = pre[now];
for(int i=0; i<edge[now].size(); i++){
if(edge[now][i] == par) continue;
low[now] = min(low[now], dfs(edge[now][i], now, i));
}
if(low[now] == pre[now] && par != -1){
bridge.PB(MP(now, par));
canUse[par][idx] = false;
for(int i=0; i<edge[now].size(); i++)
if(edge[now][i] == par) canUse[now][i] = false;
}
return low[now];
}
UnionFind uf;
bool flg[100000] ={};
void bfs(int now){
if(flg[now]) return;
queue<int> que;
que.push(now);
flg[now] = false;
while(!que.empty()){
int now = que.front();
que.pop();
for(int i=0; i<edge[now].size(); i++){
if(!canUse[now][i]){
continue;
}
if(flg[edge[now][i]]) continue;
uf.unite(now, edge[now][i]);
flg[edge[now][i]] = true;
que.push(edge[now][i]);
}
}
}
int main(){
cin >> N >> M;
for(int i=0; i<M; i++){
int a, b;
cin >> a >> b;
edge[a-1].PB(b-1);
canUse[a-1].PB(true);
edge[b-1].PB(a-1);
canUse[b-1].PB(true);
}
for(int i=0; i<N; i++) sz[i] = edge[i].size();
for(int i=0; i<N; i++) low[i] = INT_MAX;
dfs(0,-1,-1);
uf.init(N);
for(int i=0; i<N; i++) bfs(0);
for(int i=1; i<N; i++) assert(pre[i] != 0);
LL ans = N*(N-1)*(N-2);
cout << ans << endl;
}
Compilation message
count_triplets.cpp: In function 'int dfs(int, int, int)':
count_triplets.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
count_triplets.cpp:62:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++)
~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void bfs(int)':
count_triplets.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
25056 KB |
Output is correct |
| 2 |
Correct |
251 ms |
25712 KB |
Output is correct |
| 3 |
Runtime error |
246 ms |
40432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
16652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
265 ms |
16764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
