#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int inN, inM;
vector<int> inGR[100007];
void initialize() {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0); cerr.tie(0);
if (fopen("FILE.INP", "r")) {
freopen("FILE.INP", "r", stdin);
freopen("FILE.OUT", "w", stdout);
}
cin >> inN >> inM;
for(int i = 1, u, v; i <= inM; ++i) {
cin >> u >> v;
inGR[u].push_back(v);
inGR[v].push_back(u);
}
}
int type_determine() {
if (inN == 10) return 1;
if (inN == 50) return 2;
}
namespace subtask1 {
int N, M;
bool havepath[17][17][17], visited[17];
vector<int> GR[100007];
ll ans = 0;
void backtrack2(ll finish, ll mid, ll start) {
if (finish != mid) {
havepath[start][mid][finish] = 1;
}
for(int nxtfinish : GR[finish]) {
if (visited[nxtfinish]) continue;
visited[nxtfinish] = 1;
backtrack2(nxtfinish, mid, start);
visited[nxtfinish] = 0;
}
}
void backtrack(ll mid, ll start) {
if (mid != start) {
backtrack2(mid, mid, start);
}
for(int nxtmid : GR[mid]) {
if (visited[nxtmid]) continue;
visited[nxtmid] = 1;
backtrack(nxtmid, start);
visited[nxtmid] = 0;
}
}
void preprocess() {
N = inN;
M = inM;
for(int i = 1; i <= N; ++i) GR[i] = inGR[i];
}
void solve() {
for(int i = 1; i <= N; ++i) {
visited[i] = 1;
backtrack(i, i);
visited[i] = 0;
}
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
for(int k = 1; k <= N; ++k) {
ans += havepath[i][j][k];
}
}
}
cout << ans << endl;
}
void process() {
preprocess();
solve();
}
}
namespace subtask3 {
int N, M, CpnCnt, cpn[100007], sz[100007], type[100007];
vector<int> GR[100007];
void preprocess() {
N = inN;
M = inM;
for(int i = 1; i <= N; ++i) GR[i] = inGR[i];
}
void Dfs(ll u, ll last) {
cpn[u] = CpnCnt;
for(int v : GR[u]) {
if (v == last) continue;
if (!cpn[v]) Dfs(v, u);
else type[CpnCnt] = 1;
}
}
void solve() {
for(int i = 1; i <= N; ++i) {
if (!cpn[i]) {
CpnCnt++;
Dfs(i, 0);
}
}
for(int i = 1; i <= N; ++i) {
sz[cpn[i]]++;
}
ll ans = 0;
for(int i = 1; i <= CpnCnt; ++i) {
ll k = sz[i];
//cerr << i << " " << k << endl;
if (!type[i]) ans += (k * (k - 1) * (k - 2)) / 6;
else ans += ((k - 1) * (k - 2)) / 2 * k;
}
cout << ans * 2;
}
void process() {
preprocess();
solve();
}
}
namespace subtask5 {
int N, M;
vector<int> GR[100007];
int visited[100007], sz[100007];
ll ans = 0;
void Dfs(int u) {
visited[u] = 1;
for(int v : GR[u]) {
if (visited[v]) continue;
Dfs(v);
sz[u] += sz[v];
}
sz[u]++;
}
void Dfs2(int u, int last, int root) {
//cerr << u << " " << (sz[root] - sz[u]) << " " << (sz[u] - 1) << endl;
ans += (sz[root] - sz[u]) * (sz[u] - 1);
for(int v : GR[u]) {
if (v == last) continue;
Dfs2(v, u, root);
}
}
void preprocess() {
N = inN;
M = inM;
for(int i = 1; i <= N; ++i) GR[i] = inGR[i];
}
void solve() {
for(int i = 1; i <= N; ++i) {
if (!visited[i]) {
Dfs(i);
Dfs2(i, 0, i);
}
}
// for(int i = 1; i <= N; ++i) {
// cerr << i << " " << sz[i] << endl;
// }
cout << ans * 2;
}
void process() {
preprocess();
solve();
}
}
int main() {
initialize();
subtask5 :: process();
// cout << 10 << " " << (100 * 99) / 2 << endl;
// for(int i = 1; i <= 100; ++i) {
// for(int j = 1; j <= i - 1; ++j) {
// cout << i << " " << j << endl;
// }
// }
}
Compilation message
count_triplets.cpp: In function 'void initialize()':
count_triplets.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen("FILE.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen("FILE.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int type_determine()':
count_triplets.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
28 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
783 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
783 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
885020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
18776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
18872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
783 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
783 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
