oj.uz

Submission #259360

# Submission time Handle Problem Language Result Execution time Memory
259360 2020-08-07T16:36:18 Z _7_7_ Duathlon (APIO18_duathlon) C++14
31 / 100
 257 ms 49272 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 -= 1ll * get(Cnt[j] + 1) * (cnt1[i] - 1);  				
			}
			

		ans -= 1ll * get(Sz[col2[i]] - Cnt[i]) * cnt1[i];
		ans -= 1ll * get(Sz[col2[i]] - Cnt[i] + 1) * (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 11 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 11 ms 16000 KB Output is correct
4 Correct 12 ms 16000 KB Output is correct
5 Correct 10 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 11 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 11 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 11 ms 16000 KB Output is correct
4 Correct 12 ms 16000 KB Output is correct
5 Correct 10 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Incorrect 11 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 107 ms 28384 KB Output is correct
2 Correct 91 ms 28280 KB Output is correct
3 Correct 161 ms 36840 KB Output is correct
4 Correct 140 ms 32504 KB Output is correct
5 Correct 146 ms 31864 KB Output is correct
6 Correct 169 ms 37112 KB Output is correct
7 Correct 176 ms 37240 KB Output is correct
8 Correct 159 ms 37880 KB Output is correct
9 Correct 158 ms 36728 KB Output is correct
10 Correct 176 ms 34936 KB Output is correct
11 Correct 128 ms 32804 KB Output is correct
12 Correct 133 ms 32760 KB Output is correct
13 Correct 144 ms 33016 KB Output is correct
14 Correct 122 ms 32376 KB Output is correct
15 Correct 106 ms 32376 KB Output is correct
16 Correct 107 ms 31480 KB Output is correct
17 Correct 15 ms 19968 KB Output is correct
18 Correct 16 ms 19968 KB Output is correct
19 Correct 15 ms 19968 KB Output is correct
20 Correct 15 ms 19968 KB Output is correct
21 Correct 15 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 12 ms 16384 KB Output is correct
3 Correct 11 ms 16384 KB Output is correct
4 Correct 12 ms 16384 KB Output is correct
5 Correct 14 ms 16384 KB Output is correct
6 Correct 13 ms 16384 KB Output is correct
7 Correct 12 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 12 ms 16384 KB Output is correct
14 Correct 15 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 16384 KB Output is correct
19 Correct 12 ms 16384 KB Output is correct
20 Correct 12 ms 16384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 47436 KB Output is correct
2 Correct 217 ms 47484 KB Output is correct
3 Correct 228 ms 47564 KB Output is correct
4 Correct 214 ms 47480 KB Output is correct
5 Correct 220 ms 47480 KB Output is correct
6 Correct 216 ms 49016 KB Output is correct
7 Correct 231 ms 49272 KB Output is correct
8 Correct 232 ms 48760 KB Output is correct
9 Correct 245 ms 48316 KB Output is correct
10 Correct 257 ms 47608 KB Output is correct
11 Correct 212 ms 47480 KB Output is correct
12 Correct 218 ms 47480 KB Output is correct
13 Correct 213 ms 47608 KB Output is correct
14 Correct 200 ms 45432 KB Output is correct
15 Correct 217 ms 43512 KB Output is correct
16 Correct 124 ms 36268 KB Output is correct
17 Correct 190 ms 47952 KB Output is correct
18 Correct 200 ms 48032 KB Output is correct
19 Correct 187 ms 48800 KB Output is correct
20 Correct 243 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 12 ms 16384 KB Output is correct
3 Incorrect 11 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 217 ms 47096 KB Output is correct
3 Incorrect 218 ms 39160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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