oj.uz

Submission #259167

# Submission time Handle Problem Language Result Execution time Memory
259167 2020-08-07T09:32:49 Z _7_7_ Duathlon (APIO18_duathlon) C++14
23 / 100
 652 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 if (!was[to])
				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:112: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 Runtime error 652 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 652 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 11940 KB Output is correct
2 Correct 70 ms 12028 KB Output is correct
3 Correct 74 ms 12056 KB Output is correct
4 Correct 81 ms 12024 KB Output is correct
5 Correct 82 ms 11988 KB Output is correct
6 Correct 85 ms 13944 KB Output is correct
7 Correct 84 ms 13560 KB Output is correct
8 Correct 95 ms 13240 KB Output is correct
9 Correct 81 ms 12796 KB Output is correct
10 Correct 70 ms 12024 KB Output is correct
11 Correct 83 ms 12024 KB Output is correct
12 Correct 82 ms 12156 KB Output is correct
13 Correct 81 ms 12024 KB Output is correct
14 Correct 72 ms 11896 KB Output is correct
15 Correct 65 ms 11768 KB Output is correct
16 Correct 42 ms 11128 KB Output is correct
17 Correct 49 ms 12140 KB Output is correct
18 Correct 52 ms 12196 KB Output is correct
19 Correct 45 ms 12272 KB Output is correct
20 Correct 45 ms 12136 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Incorrect 2 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 81 ms 12024 KB Output is correct
2 Correct 92 ms 11896 KB Output is correct
3 Incorrect 128 ms 13176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 652 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 652 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -