oj.uz

Submission #259365

# Submission time Handle Problem Language Result Execution time Memory
259365 2020-08-07T16:42:18 Z _7_7_ Duathlon (APIO18_duathlon) C++14
31 / 100
 240 ms 49404 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, k, col[N], cnt[N], K, Sz[N], par[N], cnt1[N];
int tin[N], fup[N], timer, col1[N], kk, Cnt[N], col2[N];
unordered_set < int > gg[N], f[N];
vi g[N], comp, G[N];
ll ans;


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

	for (auto to : g[v]) {
		if (to == p)
			continue;
		if (tin[to])
			fup[v] = min(fup[v], tin[to]);
		else {
			dfs(to, v);
			fup[v] = min(fup[v], fup[to]);
			if (fup[to] > tin[v]) {
				gg[v].insert(to); 
				gg[to].insert(v);
			}
		}	
	}
}


void dfs1 (int v, int c) {
	col1[v]	= c;
	col2[c] = col[v];
	++cnt1[c];
	for (auto to : g[v])
		if (!col1[to] && !gg[v].count(to))
			dfs1(to, c);
}

void dfs2 (int v, int p = 0) {
	Cnt[v] = cnt1[v];
	
	Sz[col2[v]] += cnt1[v];
	par[v] = p;

	for (auto to : G[v])
		if (to != p) {
			dfs2(to, v); 
			Cnt[v] += Cnt[to];
		}					                     

}
 
ll get (int x) {
	return x * 1ll * (x - 1);
}

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)
		if (!col[i]) {
			++k;
			dfs(i); 
			ans += cnt[k] * 1ll * (cnt[k] - 1) * (cnt[k] - 2);
		}


	for (int i = 1; i <= n; ++i)
		if (!col1[i]) {
			++kk;
			dfs1(i, kk); 
		}


	for (int i = 1; i <= n; ++i) {
		for (auto j : g[i])
			if (col1[i] != col1[j] && !f[col1[i]].count(col1[j])) {
				f[col1[i]].insert(col1[j]);
				G[col1[i]].pb(col1[j]);
			}	
	}			

	for (int i = 1; i <= kk; ++i)
		if (!Cnt[i]) 
			dfs2(i);  
		
		

	for (int i = 1; i <= kk; ++i) {
		for (auto j : G[i])
			if (j != par[i]) {
				ans -= 1ll * get(Cnt[j]) * cnt1[i];  
				ans -= 2ll * Cnt[j] * (cnt1[i] - 1);  				
			}
			

		ans -= 1ll * get(Sz[col2[i]] - Cnt[i]) * cnt1[i];
		ans -= 2ll * (Sz[col2[i]] - Cnt[i]) * (cnt1[i] - 1);
	}

	cout << ans << endl;
	
}

Compilation message

count_triplets.cpp:101: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 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 10 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 10 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 28236 KB Output is correct
2 Correct 102 ms 28280 KB Output is correct
3 Correct 164 ms 36856 KB Output is correct
4 Correct 125 ms 32504 KB Output is correct
5 Correct 127 ms 31864 KB Output is correct
6 Correct 156 ms 37116 KB Output is correct
7 Correct 161 ms 37228 KB Output is correct
8 Correct 163 ms 37752 KB Output is correct
9 Correct 161 ms 36728 KB Output is correct
10 Correct 151 ms 34936 KB Output is correct
11 Correct 131 ms 32760 KB Output is correct
12 Correct 132 ms 32760 KB Output is correct
13 Correct 120 ms 33016 KB Output is correct
14 Correct 122 ms 32364 KB Output is correct
15 Correct 102 ms 32376 KB Output is correct
16 Correct 108 ms 31632 KB Output is correct
17 Correct 16 ms 19968 KB Output is correct
18 Correct 15 ms 19968 KB Output is correct
19 Correct 15 ms 19968 KB Output is correct
20 Correct 16 ms 19968 KB Output is correct
21 Correct 16 ms 19968 KB Output is correct
22 Correct 15 ms 19968 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16384 KB Output is correct
2 Correct 11 ms 16396 KB Output is correct
3 Correct 12 ms 16384 KB Output is correct
4 Correct 12 ms 16384 KB Output is correct
5 Correct 12 ms 16384 KB Output is correct
6 Correct 12 ms 16384 KB Output is correct
7 Correct 14 ms 16384 KB Output is correct
8 Correct 12 ms 16384 KB Output is correct
9 Correct 12 ms 16384 KB Output is correct
10 Correct 12 ms 16384 KB Output is correct
11 Correct 12 ms 16384 KB Output is correct
12 Correct 15 ms 16384 KB Output is correct
13 Correct 15 ms 16384 KB Output is correct
14 Correct 12 ms 16384 KB Output is correct
15 Correct 12 ms 16256 KB Output is correct
16 Correct 12 ms 16256 KB Output is correct
17 Correct 12 ms 16384 KB Output is correct
18 Correct 12 ms 16352 KB Output is correct
19 Correct 12 ms 16384 KB Output is correct
20 Correct 14 ms 16384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 47480 KB Output is correct
2 Correct 217 ms 47480 KB Output is correct
3 Correct 215 ms 47480 KB Output is correct
4 Correct 221 ms 47608 KB Output is correct
5 Correct 217 ms 47480 KB Output is correct
6 Correct 216 ms 48888 KB Output is correct
7 Correct 229 ms 49404 KB Output is correct
8 Correct 225 ms 48760 KB Output is correct
9 Correct 219 ms 48248 KB Output is correct
10 Correct 215 ms 47536 KB Output is correct
11 Correct 209 ms 47480 KB Output is correct
12 Correct 228 ms 47480 KB Output is correct
13 Correct 240 ms 47480 KB Output is correct
14 Correct 214 ms 45560 KB Output is correct
15 Correct 180 ms 43296 KB Output is correct
16 Correct 124 ms 36088 KB Output is correct
17 Correct 178 ms 47956 KB Output is correct
18 Correct 189 ms 47948 KB Output is correct
19 Correct 190 ms 48668 KB Output is correct
20 Correct 188 ms 48376 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 47480 KB Output is correct
2 Correct 226 ms 47096 KB Output is correct
3 Incorrect 193 ms 38904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 10 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 11 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 10 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -