oj.uz

Submission #259166

# Submission time Handle Problem Language Result Execution time Memory
259166 2020-08-07T09:32:33 Z _7_7_ Duathlon (APIO18_duathlon) C++14
23 / 100
 685 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[v])
				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 685 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 685 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 105 ms 16928 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 3 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 2 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 3 ms 2816 KB Output is correct
11 Correct 2 ms 2816 KB Output is correct
12 Correct 2 ms 2816 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Correct 2 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 68 ms 12024 KB Output is correct
2 Correct 71 ms 12024 KB Output is correct
3 Correct 73 ms 12024 KB Output is correct
4 Correct 70 ms 12024 KB Output is correct
5 Correct 67 ms 11948 KB Output is correct
6 Correct 85 ms 13944 KB Output is correct
7 Correct 77 ms 13688 KB Output is correct
8 Correct 80 ms 13180 KB Output is correct
9 Correct 89 ms 12716 KB Output is correct
10 Correct 73 ms 12024 KB Output is correct
11 Correct 72 ms 12028 KB Output is correct
12 Correct 67 ms 12152 KB Output is correct
13 Correct 67 ms 12024 KB Output is correct
14 Correct 68 ms 11896 KB Output is correct
15 Correct 66 ms 11768 KB Output is correct
16 Correct 49 ms 11128 KB Output is correct
17 Correct 50 ms 12140 KB Output is correct
18 Correct 54 ms 12136 KB Output is correct
19 Correct 56 ms 12256 KB Output is correct
20 Correct 61 ms 12136 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 84 ms 12028 KB Output is correct
2 Correct 68 ms 11896 KB Output is correct
3 Incorrect 88 ms 13048 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 685 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 685 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -