oj.uz

Submission #259672

# Submission time Handle Problem Language Result Execution time Memory
259672 2020-08-08T07:38:52 Z _7_7_ Duathlon (APIO18_duathlon) C++14
66 / 100
 255 ms 50980 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, S[N], s[N];


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 <= n; ++i) {
	    s[i] = 1;
	    for (auto j : g[i]) {
			if (col1[i] == col1[j])
				continue;
			int cur;
			if (Cnt[col1[i]] > Cnt[col1[j]])
				cur = Cnt[col1[j]];
			else
				cur = cnt[col[i]] - Cnt[col1[i]];
			s[i] += cur;
			ans -= get(cur);
//			cerr << i << ' ' << j << ' ' << cur << endl;
	    }

		S[col1[i]] += get(s[i]);
	}

	for (int i = 1; i <= n; ++i) 
		ans -= S[col1[i]] - get(s[i]);		
	


	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 11 ms 16000 KB Output is correct
3 Correct 11 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 12 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Incorrect 11 ms 16000 KB Output isn't correct
9 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 11 ms 16000 KB Output is correct
3 Correct 11 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 12 ms 16000 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Incorrect 11 ms 16000 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 27776 KB Output is correct
2 Correct 95 ms 27768 KB Output is correct
3 Correct 171 ms 36728 KB Output is correct
4 Correct 149 ms 33528 KB Output is correct
5 Correct 153 ms 32888 KB Output is correct
6 Correct 199 ms 38264 KB Output is correct
7 Correct 166 ms 38520 KB Output is correct
8 Correct 166 ms 39016 KB Output is correct
9 Correct 177 ms 37992 KB Output is correct
10 Correct 157 ms 36088 KB Output is correct
11 Correct 135 ms 34040 KB Output is correct
12 Correct 136 ms 34040 KB Output is correct
13 Correct 141 ms 34204 KB Output is correct
14 Correct 143 ms 33692 KB Output is correct
15 Correct 112 ms 33784 KB Output is correct
16 Correct 106 ms 32888 KB Output is correct
17 Correct 17 ms 21504 KB Output is correct
18 Correct 17 ms 21504 KB Output is correct
19 Correct 17 ms 21504 KB Output is correct
20 Correct 17 ms 21504 KB Output is correct
21 Correct 17 ms 21504 KB Output is correct
22 Correct 17 ms 21504 KB Output is correct

Subtask #4
10.0 / 10.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 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 13 ms 16384 KB Output is correct
8 Correct 12 ms 16384 KB Output is correct
9 Correct 13 ms 16384 KB Output is correct
10 Correct 13 ms 16384 KB Output is correct
11 Correct 12 ms 16384 KB Output is correct
12 Correct 12 ms 16384 KB Output is correct
13 Correct 13 ms 16384 KB Output is correct
14 Correct 12 ms 16384 KB Output is correct
15 Correct 12 ms 16384 KB Output is correct
16 Correct 13 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 11 ms 16384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 47736 KB Output is correct
2 Correct 237 ms 49028 KB Output is correct
3 Correct 248 ms 49020 KB Output is correct
4 Correct 241 ms 49144 KB Output is correct
5 Correct 247 ms 49016 KB Output is correct
6 Correct 220 ms 50424 KB Output is correct
7 Correct 238 ms 50980 KB Output is correct
8 Correct 241 ms 50424 KB Output is correct
9 Correct 255 ms 49784 KB Output is correct
10 Correct 228 ms 49016 KB Output is correct
11 Correct 239 ms 48980 KB Output is correct
12 Correct 254 ms 49016 KB Output is correct
13 Correct 236 ms 49016 KB Output is correct
14 Correct 197 ms 46968 KB Output is correct
15 Correct 182 ms 44920 KB Output is correct
16 Correct 119 ms 37580 KB Output is correct
17 Correct 185 ms 49616 KB Output is correct
18 Correct 186 ms 49444 KB Output is correct
19 Correct 188 ms 50332 KB Output is correct
20 Correct 182 ms 49912 KB Output is correct

Subtask #6
15.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 Correct 13 ms 16256 KB Output is correct
4 Correct 12 ms 16320 KB Output is correct
5 Correct 12 ms 16128 KB Output is correct
6 Correct 12 ms 16128 KB Output is correct
7 Correct 11 ms 16128 KB Output is correct
8 Correct 11 ms 16128 KB Output is correct
9 Correct 11 ms 16128 KB Output is correct
10 Correct 11 ms 16128 KB Output is correct
11 Correct 11 ms 16128 KB Output is correct
12 Correct 12 ms 16256 KB Output is correct
13 Correct 12 ms 16256 KB Output is correct
14 Correct 11 ms 16256 KB Output is correct
15 Correct 12 ms 16256 KB Output is correct
16 Correct 12 ms 16256 KB Output is correct
17 Correct 11 ms 16256 KB Output is correct
18 Correct 11 ms 16268 KB Output is correct
19 Correct 11 ms 16256 KB Output is correct
20 Correct 12 ms 16128 KB Output is correct
21 Correct 11 ms 16256 KB Output is correct
22 Correct 12 ms 16256 KB Output is correct
23 Correct 12 ms 16256 KB Output is correct
24 Correct 13 ms 16256 KB Output is correct
25 Correct 11 ms 16128 KB Output is correct
26 Correct 12 ms 16128 KB Output is correct
27 Correct 11 ms 16128 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 47736 KB Output is correct
2 Correct 234 ms 48632 KB Output is correct
3 Correct 217 ms 40440 KB Output is correct
4 Correct 169 ms 33656 KB Output is correct
5 Correct 157 ms 28408 KB Output is correct
6 Correct 145 ms 26620 KB Output is correct
7 Correct 140 ms 25612 KB Output is correct
8 Correct 110 ms 24696 KB Output is correct
9 Correct 104 ms 24184 KB Output is correct
10 Correct 94 ms 23928 KB Output is correct
11 Correct 92 ms 23416 KB Output is correct
12 Correct 89 ms 23032 KB Output is correct
13 Correct 94 ms 23164 KB Output is correct
14 Correct 94 ms 24444 KB Output is correct
15 Correct 220 ms 42756 KB Output is correct
16 Correct 207 ms 42104 KB Output is correct
17 Correct 184 ms 38268 KB Output is correct
18 Correct 192 ms 37752 KB Output is correct
19 Correct 173 ms 33784 KB Output is correct
20 Correct 180 ms 33784 KB Output is correct
21 Correct 186 ms 33656 KB Output is correct
22 Correct 154 ms 31608 KB Output is correct
23 Correct 123 ms 29304 KB Output is correct
24 Correct 176 ms 40440 KB Output is correct
25 Correct 201 ms 40952 KB Output is correct
26 Correct 165 ms 36388 KB Output is correct
27 Correct 180 ms 36856 KB Output is correct

Subtask #8
0 / 8.0

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