oj.uz

Submission #259165

# Submission time Handle Problem Language Result Execution time Memory
259165 2020-08-07T09:29:21 Z _7_7_ Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 1e5 + 12;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;
 
int n, m, v, u, cnt[N], p[N], col[N], Sz[N], Cnt[N], par[N];
int tin[N], tout[N], timer, d[N], ans, k;
bool was[N];
vi g[N];

bool upper (int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int get (int v) {
	return v == p[v] ? v :  p[v] = get(p[v]);
}


void merge (int v, int u) {
	v = get(v), u = get(u);
	if (v == u)
		return;

	if (Cnt[v] < Cnt[u])
		swap(v, u);

	p[u] = v;
	Cnt[v] += Cnt[u];
}


void dfs (int v, int p = 0) {
	par[v] = p;
	tin[v] = ++timer;
	cnt[v] = 1;
	col[v] = k;
	++Sz[k];

	for (auto to : g[v])
		if (!col[to]) {
			dfs(to, v);
			cnt[v] += cnt[to];
		}

	tout[v] = timer;
} 

int V;
void dfs1 (int v, int u) {
	for (auto to : g[v])
		if (to != par[v] && upper(to, u)) {			
			if ((V == v && to == u) || (to == V && v == u))
				continue;
			dfs1(to, u); 
			d[v] = d[to] + 1;
			merge(v, to);
		}
}

void dfs2 (int v) {
	was[v] = 1;

	for (auto to : g[v])
		if (to != par[v]) {
			if (upper(to, v)) {
				V = to;
				dfs1(to, v);				
			} else
				dfs2(to);
		}
}

 
main () {
	fastio
	cin >> n >> m;
	while (m--) {
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}

	for (int i = 1; i <= n; ++i) {
	    p[i] = i;
		Cnt[i] = 1;
		if (!col[i]) {
		    ++k;
			dfs(i); 
			ans += Sz[k] * (Sz[k] - 1) * (Sz[k] - 2);
		}
	}


	for (int i = 1; i <= n; ++i)
		if (!was[i])
			dfs2(i);
	

	for (int i = 1; i <= n; ++i) {
		for (auto j : g[i])
			if (j != par[i])
				ans -= cnt[j] * (cnt[j] - 1);

		ans -= (Sz[col[i]] - cnt[i]) * (Sz[col[i]] - cnt[i] - 1);

	    cerr << i << ' ' << d[i] << endl;
		ans += d[i] * (d[i] - 1);
		ans += (Cnt[get(i)] - d[i] - 1) * (Cnt[get(i)] - d[i] - 2);
	}
	
	
	cout << ans << endl;
}

Compilation message

count_triplets.cpp:113:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1118 ms 1048580 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 1118 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 912 ms 22464 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 16 ms 2816 KB Output is correct
2 Correct 16 ms 2920 KB Output is correct
3 Correct 11 ms 2900 KB Output is correct
4 Correct 10 ms 2816 KB Output is correct
5 Correct 10 ms 2816 KB Output is correct
6 Correct 10 ms 2816 KB Output is correct
7 Correct 14 ms 2816 KB Output is correct
8 Correct 10 ms 2816 KB Output is correct
9 Correct 14 ms 2816 KB Output is correct
10 Correct 10 ms 2816 KB Output is correct
11 Correct 16 ms 2816 KB Output is correct
12 Correct 9 ms 2816 KB Output is correct
13 Correct 15 ms 2816 KB Output is correct
14 Correct 10 ms 2816 KB Output is correct
15 Correct 9 ms 2908 KB Output is correct
16 Correct 15 ms 2816 KB Output is correct
17 Correct 10 ms 2816 KB Output is correct
18 Correct 14 ms 2816 KB Output is correct
19 Correct 10 ms 2816 KB Output is correct
20 Correct 9 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 14084 KB Output is correct
2 Correct 810 ms 14072 KB Output is correct
3 Correct 827 ms 14360 KB Output is correct
4 Correct 842 ms 14208 KB Output is correct
5 Correct 837 ms 14108 KB Output is correct
6 Correct 930 ms 16120 KB Output is correct
7 Correct 855 ms 15740 KB Output is correct
8 Correct 870 ms 15480 KB Output is correct
9 Correct 829 ms 14840 KB Output is correct
10 Correct 813 ms 14200 KB Output is correct
11 Correct 831 ms 14072 KB Output is correct
12 Correct 837 ms 14200 KB Output is correct
13 Correct 834 ms 14212 KB Output is correct
14 Correct 860 ms 13756 KB Output is correct
15 Correct 816 ms 13560 KB Output is correct
16 Correct 789 ms 12536 KB Output is correct
17 Correct 789 ms 14444 KB Output is correct
18 Correct 800 ms 14280 KB Output is correct
19 Correct 789 ms 14400 KB Output is correct
20 Correct 817 ms 14312 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 14004 KB Output is correct
2 Correct 836 ms 14200 KB Output is correct
3 Execution timed out 1004 ms 15392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1118 ms 1048580 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 1118 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -