Submission #172525

# Submission time Handle Problem Language Result Execution time Memory
172525 2020-01-01T20:24:20 Z eggag32 Duathlon (APIO18_duathlon) C++17
5 / 100
1000 ms 1048580 KB
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int n, m;
vi vis;
vi g[100005];

bool dfs(int cur, int mid, int fin, bool fnd, vi vis){
	//debug(cur);
	//debug(mid);
	//debug(fin);
	//debug(fnd);
	vis[cur] = 1;
	if(cur == mid) fnd = 1;
	if(cur == fin){
		if(fnd) return 1;
		return 0;
	}
	int ret = 0;
	for(int u : g[cur]) if(!vis[u]){
		ret |= dfs(u, mid, fin, fnd, vis);
		if(ret) break;
	}
	return ret;
}

bool check(int st, int mid, int fin){
	vis.assign(n, 0);
	return dfs(st, mid, fin, 0, vis);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin >> n >> m;
	rep(i, m){
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	//debug(check(1, 3, 2));
	int ans = 0;
	rep(i, n) repn(k, i + 1, n) rep(j, n) if(j != i && j != k){
		if(check(i, j, k)){
			//cout << i << " " << j << " " << k << endl;
			ans++;
			ans++; //for (k, j, i)
		}
	}
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2812 KB Output is correct
11 Correct 5 ms 2680 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct
13 Correct 5 ms 2680 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 5 ms 2708 KB Output is correct
17 Correct 5 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 5 ms 2680 KB Output is correct
23 Correct 5 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 4 ms 2684 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2680 KB Output is correct
28 Correct 4 ms 2680 KB Output is correct
29 Correct 4 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2680 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 4 ms 2684 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2812 KB Output is correct
11 Correct 5 ms 2680 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct
13 Correct 5 ms 2680 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 5 ms 2708 KB Output is correct
17 Correct 5 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 5 ms 2680 KB Output is correct
23 Correct 5 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 4 ms 2684 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2680 KB Output is correct
28 Correct 4 ms 2680 KB Output is correct
29 Correct 4 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2680 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 4 ms 2684 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 8 ms 2680 KB Output is correct
37 Correct 16 ms 2680 KB Output is correct
38 Execution timed out 1064 ms 2680 KB Time limit exceeded
39 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 894 ms 1048580 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 1056 ms 2808 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 18244 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 2808 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 16664 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2812 KB Output is correct
11 Correct 5 ms 2680 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct
13 Correct 5 ms 2680 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 5 ms 2708 KB Output is correct
17 Correct 5 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 5 ms 2680 KB Output is correct
23 Correct 5 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 4 ms 2684 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2680 KB Output is correct
28 Correct 4 ms 2680 KB Output is correct
29 Correct 4 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2680 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 4 ms 2684 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 8 ms 2680 KB Output is correct
37 Correct 16 ms 2680 KB Output is correct
38 Execution timed out 1064 ms 2680 KB Time limit exceeded
39 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2812 KB Output is correct
11 Correct 5 ms 2680 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct
13 Correct 5 ms 2680 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 5 ms 2708 KB Output is correct
17 Correct 5 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 5 ms 2680 KB Output is correct
23 Correct 5 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 4 ms 2684 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2680 KB Output is correct
28 Correct 4 ms 2680 KB Output is correct
29 Correct 4 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2680 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 4 ms 2684 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 8 ms 2680 KB Output is correct
37 Correct 16 ms 2680 KB Output is correct
38 Execution timed out 1064 ms 2680 KB Time limit exceeded
39 Halted 0 ms 0 KB -