oj.uz

Submission #259173

# Submission time Handle Problem Language Result Execution time Memory
259173 2020-08-07T10:08:42 Z _7_7_ Duathlon (APIO18_duathlon) C++14
31 / 100
 637 ms 1048576 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, dw[N], up[N];
set < pii > q;
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);
				dw[get(v)] = cnt[v] - 1;
				up[get(v)] = Sz[col[v]] - cnt[to];
			} else if (!was[to])
				dfs2(to);
			else {
				q.insert({v, to});	 
				q.insert({to, v});	 
			}
		}
}

 
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) {
//	    cout << i << endl;
		for (auto j : g[i])
			if (j != par[i] && !q.count(mp(i, j))) {
				ans -= cnt[j] * (cnt[j] - 1);  
//				cout << " - " << cnt[j] << endl;
			}

		ans -= (Sz[col[i]] - cnt[i]) * (Sz[col[i]] - cnt[i] - 1);
//		cout << " - " << (Sz[col[i]] - cnt[i]) << endl;

		ans += d[i] * (d[i] - 1);
//		cout << " + " << d[i] << endl;
//		cout << " + " << (Cnt[get(i)] - d[i] - 1) << endl << endl;

		ans += (Cnt[get(i)] - d[i] - 1) * (Cnt[get(i)] - d[i] - 2);

		if (d[i]) {
			ans += 2*(d[i] - 1) * dw[get(i)]; 
//			cout << " + " << (d[i] - 1) << ' ' << dw[get(i)] << endl;
		}

		if (Cnt[get(i)] - d[i] > 1) {
			ans += 2*(Cnt[get(i)] - d[i] - 2) * up[get(i)]; 
//			cout << " + " << (Cnt[get(i)] - d[i] - 2) << ' ' << up[get(i)] << endl;
		}
	}
	
	
	cout << ans << endl;
}

Compilation message

count_triplets.cpp:119: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 637 ms 1048576 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 637 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 24696 KB Output is correct
2 Correct 116 ms 24824 KB Output is correct
3 Correct 107 ms 18552 KB Output is correct
4 Correct 110 ms 21624 KB Output is correct
5 Correct 130 ms 16696 KB Output is correct
6 Correct 100 ms 16376 KB Output is correct
7 Correct 99 ms 14840 KB Output is correct
8 Correct 98 ms 15744 KB Output is correct
9 Correct 98 ms 13560 KB Output is correct
10 Correct 104 ms 14848 KB Output is correct
11 Correct 93 ms 15224 KB Output is correct
12 Correct 91 ms 14968 KB Output is correct
13 Correct 95 ms 15224 KB Output is correct
14 Correct 121 ms 14840 KB Output is correct
15 Correct 59 ms 14456 KB Output is correct
16 Correct 61 ms 14328 KB Output is correct
17 Correct 7 ms 9088 KB Output is correct
18 Correct 7 ms 9088 KB Output is correct
19 Correct 7 ms 9064 KB Output is correct
20 Correct 7 ms 9088 KB Output is correct
21 Correct 7 ms 9088 KB Output is correct
22 Correct 7 ms 9088 KB Output is correct

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 2944 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 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 2 ms 2816 KB Output is correct
12 Correct 3 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 3 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 12152 KB Output is correct
2 Correct 87 ms 12152 KB Output is correct
3 Correct 88 ms 12040 KB Output is correct
4 Correct 77 ms 12152 KB Output is correct
5 Correct 68 ms 12152 KB Output is correct
6 Correct 98 ms 15736 KB Output is correct
7 Correct 90 ms 14840 KB Output is correct
8 Correct 87 ms 14072 KB Output is correct
9 Correct 99 ms 13432 KB Output is correct
10 Correct 77 ms 12156 KB Output is correct
11 Correct 74 ms 12048 KB Output is correct
12 Correct 71 ms 12152 KB Output is correct
13 Correct 71 ms 12152 KB Output is correct
14 Correct 65 ms 12024 KB Output is correct
15 Correct 60 ms 11768 KB Output is correct
16 Correct 54 ms 11128 KB Output is correct
17 Correct 45 ms 12268 KB Output is correct
18 Correct 52 ms 12392 KB Output is correct
19 Correct 44 ms 12256 KB Output is correct
20 Correct 45 ms 12264 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 2944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12108 KB Output is correct
2 Correct 81 ms 12040 KB Output is correct
3 Incorrect 170 ms 16812 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 637 ms 1048576 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 637 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -