oj.uz

Submission #764080

# Submission time Handle Problem Language Result Execution time Memory
764080 2023-06-23T06:58:28 Z OrazB Duathlon (APIO18_duathlon) C++14
23 / 100
 925 ms 1048576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 2000005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

bool vis[N];
ll sub[N], sum;
vector<int> E[N];
vector<int> vec;

void dfs(int nd){
	vis[nd] = sub[nd] = 1;
	for (auto i : E[nd]){
		if (!vis[i]){
			dfs(i);
			sub[nd] += sub[i];
		} 
	}
}
void dfsz(int nd, int pr, ll sz){
	sum += (sz-sub[nd])*(sub[nd]-1)*2;
	for (auto i : E[nd]){
		if (i == pr) continue;
		dfsz(i,nd,sz);
		sum += (sub[nd]-sub[i]-1)*sub[i];
	}
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	while(m--){
		int u, v;
		cin >> u >> v;
		E[u].pb(v);
		E[v].pb(u);
	}
	for (int i = 1; i <= n; i++){
		if (!vis[i]){
			dfs(i);
			dfsz(i, 0, sub[i]);
		}
	}
	cout << sum << '\n';
}

Compilation message

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:28:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   28 |  vis[nd] = sub[nd] = 1;
      |            ~~~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048576 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 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47272 KB Output is correct
2 Correct 23 ms 47256 KB Output is correct
3 Correct 23 ms 47340 KB Output is correct
4 Correct 24 ms 47412 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 24 ms 47300 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 24 ms 47316 KB Output is correct
9 Correct 23 ms 47288 KB Output is correct
10 Correct 24 ms 47316 KB Output is correct
11 Correct 26 ms 47340 KB Output is correct
12 Correct 24 ms 47312 KB Output is correct
13 Correct 28 ms 47248 KB Output is correct
14 Correct 24 ms 47308 KB Output is correct
15 Correct 23 ms 47288 KB Output is correct
16 Correct 23 ms 47260 KB Output is correct
17 Correct 25 ms 47344 KB Output is correct
18 Correct 24 ms 47260 KB Output is correct
19 Correct 24 ms 47304 KB Output is correct
20 Correct 24 ms 47324 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 51440 KB Output is correct
2 Correct 56 ms 52564 KB Output is correct
3 Correct 53 ms 52548 KB Output is correct
4 Correct 54 ms 52664 KB Output is correct
5 Correct 68 ms 52560 KB Output is correct
6 Correct 59 ms 56788 KB Output is correct
7 Correct 58 ms 55296 KB Output is correct
8 Correct 69 ms 54620 KB Output is correct
9 Correct 56 ms 53884 KB Output is correct
10 Correct 54 ms 52664 KB Output is correct
11 Correct 54 ms 52544 KB Output is correct
12 Correct 55 ms 52556 KB Output is correct
13 Correct 55 ms 52608 KB Output is correct
14 Correct 50 ms 52380 KB Output is correct
15 Correct 50 ms 52220 KB Output is correct
16 Correct 44 ms 51092 KB Output is correct
17 Correct 48 ms 52856 KB Output is correct
18 Correct 45 ms 52856 KB Output is correct
19 Correct 56 ms 52896 KB Output is correct
20 Correct 51 ms 52924 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47240 KB Output is correct
2 Correct 24 ms 47352 KB Output is correct
3 Runtime error 420 ms 1048576 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 54 ms 51408 KB Output is correct
2 Correct 60 ms 52612 KB Output is correct
3 Runtime error 518 ms 1048576 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 448 ms 1048576 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 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -