oj.uz

Submission #387957

# Submission time Handle Problem Language Result Execution time Memory
387957 2021-04-09T15:03:05 Z NurstanDuisengaliev Duathlon (APIO18_duathlon) C++14
0 / 100
 70 ms 12792 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define int ll

using namespace std;

const int N = (int)1e5 + 123;
int n, m;
vector <int> g[N];  
int used[N];
ll ans = 0, LEN = 0;
bool FindC (int v) {
 	used[v] = 1;
 	bool yes = 0;
 	LEN ++;
 	for (auto to : g[v]) {
 		if (!used[to]) {
 			yes |= FindC (to);
 		}
 		else if (used[to] == 1) {
 			yes = 1;						
 		}
 	}
 	used[v] = 2;
 	return yes;
}
main () {
    ios_base::sync_with_stdio (0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
    	int u, v;
    	cin >> u >> v;
    	g[u].pb (v);
    	g[v].pb (u);
    }
  	int maxisz = 0;
  	for (int i = 1; i <= n; i ++) {
  		maxisz = max (maxisz, sz (g[i]));
  	}
  	if (maxisz <= 2) {
  		for (int i = 1; i <= n; i ++) {
  			if (!used[i]) {
  				LEN = 0;
  				if (FindC (i)) {
  				    ans += ((LEN * 1ll * (LEN - 1) * 1ll * (LEN - 2)) / 3); 
  				}
  				else {
  					for (int j = 1; j <= LEN - 2; j ++) {
  						ans += (LEN - (j + 2) + 1) * 1ll * j;
  					}	
  				}
  			}	
  		}	
  		cout << ans;
  		return 0;
  	}
  	
	return 0;
}

Compilation message

count_triplets.cpp:30:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main () {
      |       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 6344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 6276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -