oj.uz

Submission #969079

# Submission time Handle Problem Language Result Execution time Memory
969079 2024-04-24T13:13:24 Z c2zi6 Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, m;
VVI gp;

ll ans;
VI sbt;
VI vis;
int dfs1(int u, int p = -1) {
	vis[u] = true;
	sbt[u] = 1;
	for (int v : gp[u]) if (v != p) sbt[u] += dfs1(v, u);
	return sbt[u];
}
ll An2(ll n) {
	return n * (n-1);
}
void dfs2(int u, int p, int S) {
	VL a;
	a.pb(S - sbt[u]);
	for (int v : gp[u]) if (v != p) {
		dfs2(v, u, S);
		a.pb(sbt[v]);
	}
	ll cur = An2(S-1);
	for (ll x : a) cur -= An2(x);
	/* cout << u+1 << ": " << cur << endl; */
	ans += cur;
}


void solve() {
	cin >> n >> m;
	gp = VVI(n);
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gp[u].pb(v);
		gp[v].pb(u);
	}
	vis = sbt = VI(n);
	ans = 0;
	rep(u, n) if (!vis[u]) dfs1(u), dfs2(u, -1, sbt[u]);
	cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 990544 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 348 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6752 KB Output is correct
2 Correct 34 ms 8028 KB Output is correct
3 Correct 34 ms 8272 KB Output is correct
4 Correct 32 ms 7884 KB Output is correct
5 Correct 33 ms 7908 KB Output is correct
6 Correct 45 ms 16464 KB Output is correct
7 Correct 45 ms 13560 KB Output is correct
8 Correct 47 ms 12116 KB Output is correct
9 Correct 40 ms 10664 KB Output is correct
10 Correct 41 ms 8020 KB Output is correct
11 Correct 33 ms 8016 KB Output is correct
12 Correct 33 ms 8012 KB Output is correct
13 Correct 33 ms 8028 KB Output is correct
14 Correct 29 ms 7620 KB Output is correct
15 Correct 27 ms 7516 KB Output is correct
16 Correct 18 ms 6488 KB Output is correct
17 Correct 24 ms 9328 KB Output is correct
18 Correct 24 ms 9280 KB Output is correct
19 Correct 25 ms 9252 KB Output is correct
20 Correct 25 ms 9144 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 632 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 47 ms 6612 KB Output is correct
2 Correct 34 ms 8028 KB Output is correct
3 Runtime error 721 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 Execution timed out 1016 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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