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

count_triplets

#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!
*/

Subtask #1
5.0 / 5.0

#	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

Subtask #2
0 / 11.0

#	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	-

Subtask #3
0 / 8.0

#	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	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1056 ms	2808 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1069 ms	18244 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1067 ms	2808 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1068 ms	16664 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	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	-

Subtask #9
0 / 10.0

#	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	-

Submission #172525

Compilation message