oj.uz

Submission #1070946

# Submission time Handle Problem Language Result Execution time Memory
1070946 2024-08-22T21:34:06 Z pawned Duathlon (APIO18_duathlon) C++17
23 / 100
 52 ms 23572 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

const int MAX = 1e5 + 5;

int N, M;

bool vis[MAX];
vi adj[MAX];

vi kids[MAX];	// all below
ll sz[MAX];	// size of below
ll sumd[MAX];	// sum of all dists below

void dfs(int n) {
	vis[n] = true;
	sz[n] = 1;
	for (int x : adj[n]) {
		if (!vis[x]) {
			dfs(x);
			kids[n].pb(x);
			sz[n] += sz[x];
			sumd[n] += (sumd[x] + sz[x]);
		}
	}
}

int main() {
	fastIO();
	cin>>N>>M;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin>>u>>v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
/*	cout<<"sz: ";
	for (int i = 0; i < N; i++) {
		cout<<sz[i]<<" ";
	}
	cout<<endl;
	cout<<"sumd: ";
	for (int i = 0; i < N; i++) {
		cout<<sumd[i]<<" ";
	}
	cout<<endl;*/
	ll total = 0;
	for (int i = 0; i < N; i++) {
		ll sum = 0;
//		cout<<"at "<<i<<endl;
		sum += (sumd[i] - sz[i] + 1);	// go down
//		cout<<"straight down: "<<(sumd[i] - sz[i] + 1)<<endl;
		ll sum1 = 0;	// total of all (sumd + sz) below
		ll sum2 = 0;	// total of all sumd^2 below
		ll sum3 = 0;	// total of all sz below
		ll sum4 = 0;	// total of all sz^2 below
		ll sum5 = 0;	// tota of all (sumd + sz) * sz below
		for (int x : kids[i]) {
			sum1 += (sumd[x] + sz[x]);
			sum2 += (sumd[x] * sumd[x]);
			sum3 += sz[x];
			sum4 += (sz[x] * sz[x]);
			sum5 += ((sumd[x] + sz[x]) * sz[x]);
		}
//		cout<<"sums: "<<sum1<<" "<<sum2<<" "<<sum3<<" "<<sum4<<" "<<sum5<<endl;
		sum += (sum1 * sum3 - sum5);
		sum -= (sum3 * sum3 - sum4) / 2;
/*		cout<<"adding "<<(sum1 * sum3 - sum5)<<endl;
		cout<<"subtracting "<<(sum3 * sum3 - sum4) / 2<<endl;
		cout<<"sum: "<<sum<<endl;*/
		total += sum;
	}
//	cout<<"ANSWER: ";
	cout<<total * 2<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 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 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6580 KB Output is correct
3 Correct 2 ms 6500 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6488 KB Output is correct
12 Correct 2 ms 6644 KB Output is correct
13 Correct 2 ms 6488 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6624 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 3 ms 6652 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12888 KB Output is correct
2 Correct 30 ms 12880 KB Output is correct
3 Correct 41 ms 12884 KB Output is correct
4 Correct 35 ms 12660 KB Output is correct
5 Correct 28 ms 12884 KB Output is correct
6 Correct 44 ms 19372 KB Output is correct
7 Correct 39 ms 16720 KB Output is correct
8 Correct 40 ms 15700 KB Output is correct
9 Correct 31 ms 14940 KB Output is correct
10 Correct 52 ms 12884 KB Output is correct
11 Correct 32 ms 12880 KB Output is correct
12 Correct 32 ms 12892 KB Output is correct
13 Correct 28 ms 12880 KB Output is correct
14 Correct 27 ms 12636 KB Output is correct
15 Correct 26 ms 12248 KB Output is correct
16 Correct 16 ms 10840 KB Output is correct
17 Correct 19 ms 12064 KB Output is correct
18 Correct 20 ms 11976 KB Output is correct
19 Correct 24 ms 11976 KB Output is correct
20 Correct 20 ms 11868 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12764 KB Output is correct
2 Correct 36 ms 13136 KB Output is correct
3 Incorrect 36 ms 13464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 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 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -