oj.uz

Submission #259169

# Submission time Handle Problem Language Result Execution time Memory
259169 2020-08-07T09:41:07 Z _7_7_ Duathlon (APIO18_duathlon) C++14
31 / 100
 638 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;
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);
			} 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) {
		for (auto j : g[i])
			if (j != par[i] && !q.count(mp(i, j))) 
				ans -= cnt[j] * (cnt[j] - 1); 

		ans -= (Sz[col[i]] - cnt[i]) * (Sz[col[i]] - cnt[i] - 1);
		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:117: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 638 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 638 ms 1048580 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 129 ms 24872 KB Output is correct
2 Correct 120 ms 25976 KB Output is correct
3 Correct 113 ms 19704 KB Output is correct
4 Correct 128 ms 22904 KB Output is correct
5 Correct 130 ms 17656 KB Output is correct
6 Correct 127 ms 17528 KB Output is correct
7 Correct 108 ms 15992 KB Output is correct
8 Correct 117 ms 17016 KB Output is correct
9 Correct 116 ms 14712 KB Output is correct
10 Correct 119 ms 15736 KB Output is correct
11 Correct 105 ms 14584 KB Output is correct
12 Correct 104 ms 14328 KB Output is correct
13 Correct 90 ms 14456 KB Output is correct
14 Correct 94 ms 14200 KB Output is correct
15 Correct 64 ms 13560 KB Output is correct
16 Correct 61 ms 13436 KB Output is correct
17 Correct 8 ms 9088 KB Output is correct
18 Correct 7 ms 9088 KB Output is correct
19 Correct 7 ms 9088 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 4 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 4 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 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 3 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 3 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 78 ms 12024 KB Output is correct
2 Correct 72 ms 12024 KB Output is correct
3 Correct 73 ms 12024 KB Output is correct
4 Correct 76 ms 12024 KB Output is correct
5 Correct 74 ms 12028 KB Output is correct
6 Correct 100 ms 15608 KB Output is correct
7 Correct 96 ms 14840 KB Output is correct
8 Correct 107 ms 14072 KB Output is correct
9 Correct 95 ms 13304 KB Output is correct
10 Correct 77 ms 12024 KB Output is correct
11 Correct 84 ms 12008 KB Output is correct
12 Correct 80 ms 12024 KB Output is correct
13 Correct 76 ms 12024 KB Output is correct
14 Correct 73 ms 11896 KB Output is correct
15 Correct 64 ms 11768 KB Output is correct
16 Correct 40 ms 11128 KB Output is correct
17 Correct 50 ms 12140 KB Output is correct
18 Correct 51 ms 12132 KB Output is correct
19 Correct 45 ms 12256 KB Output is correct
20 Correct 54 ms 12136 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 3 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 73 ms 12024 KB Output is correct
2 Correct 86 ms 11896 KB Output is correct
3 Incorrect 166 ms 15224 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 638 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 638 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -