oj.uz

Submission #413624

# Submission time Handle Problem Language Result Execution time Memory
413624 2021-05-29T06:32:46 Z hhhhaura Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i ,a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().times_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n, ans = 0 ;
	vector<vector<int>> mp;
	vector<int> dp, sz;
	void init_(int _n) {
		n = _n, ans = 0;
		mp.assign(n + 1, vector<int>());
		dp.assign(n + 1, 0);
		sz.assign(n + 1, 0);
	}
	void dfs(int x, int par) {
		sz[x] = 1, dp[x] = 0;
		for(auto i : mp[x]) if(i != par) {
			dfs(i, x);
			dp[x] += dp[i] + sz[i];
			sz[x] += sz[i];
		}
		int temp = 0, cur = 0;
		for(auto i : mp[x]) if(i != par) {
			temp += dp[i] * (sz[x] - sz[i]);
			temp += cur * sz[i];
			cur += sz[i];
		}
		ans += temp;
		return;
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m; cin >> n >> m;
	init_(n);
	rep(i, 1, m) {
		int a, b; cin >> a >> b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	rep(i, 1, n) if(!sz[i]) dfs(i, i);
	cout << ans * 2 << "\n";
	
	return 0;
}

Compilation message

count_triplets.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
count_triplets.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
count_triplets.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 657 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 657 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8232 KB Output is correct
2 Correct 61 ms 9220 KB Output is correct
3 Correct 54 ms 9216 KB Output is correct
4 Correct 53 ms 9196 KB Output is correct
5 Correct 64 ms 9196 KB Output is correct
6 Correct 94 ms 12768 KB Output is correct
7 Correct 74 ms 11976 KB Output is correct
8 Correct 61 ms 11240 KB Output is correct
9 Correct 70 ms 10520 KB Output is correct
10 Correct 58 ms 9156 KB Output is correct
11 Correct 56 ms 9160 KB Output is correct
12 Correct 85 ms 9160 KB Output is correct
13 Correct 56 ms 9096 KB Output is correct
14 Correct 52 ms 8768 KB Output is correct
15 Correct 48 ms 8396 KB Output is correct
16 Correct 31 ms 7216 KB Output is correct
17 Correct 50 ms 9396 KB Output is correct
18 Correct 52 ms 9396 KB Output is correct
19 Correct 45 ms 9580 KB Output is correct
20 Correct 41 ms 9328 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Runtime error 743 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8300 KB Output is correct
2 Correct 69 ms 9036 KB Output is correct
3 Runtime error 923 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 657 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 657 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -