oj.uz

Submission #958536

# Submission time Handle Problem Language Result Execution time Memory
958536 2024-04-06T01:49:28 Z Cyber_Wolf Duathlon (APIO18_duathlon) C++17
0 / 100
 85 ms 39116 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 2e5+5;

vector<lg> adj[N],adj2[N], p, comps[N];
lg low[N], ans, n, m, artic[N], tin[N], tmp, vis[N], id[N], ids, sz[N], n2;

void dfs(lg src, lg par = -1)
{
	low[src] = tin[src] = ++tmp;
	n2++;
	p.push_back(src);
	for(auto it : adj[src])
	{
		if(it == par)
		{
			continue;
		}
		if(tin[it])
		{
			low[src] = min(low[src], tin[it]);
			continue;
		}
		dfs(it, src);
		low[src] = min(low[src], low[it]);
		if(low[it] >= tin[src])
		{
			artic[src] = (tin[src] > 1 || tin[it] > 2);	
			ids++;
			adj2[src].push_back(n+ids);
			while(adj2[n+ids].empty() || adj2[n+ids].back() != it)
			{
				adj2[n+ids].push_back(p.back());
				p.pop_back();
			}
		}
	}
}

void dfs2(lg src)
{
	sz[src] = (src <= n);
	vis[src] = true;
	lg x = adj2[src].size();
	for(auto it : adj2[src])
	{
		if(vis[it])	continue;
		dfs2(it);
		sz[src] += sz[it];
		if(src > n)
		{
			ans -= sz[it]*(sz[it]-1)*x;
		}
	}
	if(src > n)
	{
		ans -= (n2-sz[src])*(n2-sz[src]-1)*x;
	}
}

int main()
{
	fastio;
	cin >> n >> m;
	ans = n*(n-1)*(n-2);
	for(int i = 0; i < m; i++)
	{
		lg u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
	{
		if(tin[i])	continue;
		n2 = 0;
		dfs(i);
		dfs2(i);
	}
	cout << ans << '\n';

    return 0;
}

/*
123 c
124 c
134 c
132 x
142 x
143 x



*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 36936 KB Output is correct
2 Correct 47 ms 36940 KB Output is correct
3 Incorrect 58 ms 34260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 31048 KB Output is correct
2 Correct 63 ms 31140 KB Output is correct
3 Correct 52 ms 31060 KB Output is correct
4 Correct 75 ms 31056 KB Output is correct
5 Correct 54 ms 31056 KB Output is correct
6 Correct 63 ms 39116 KB Output is correct
7 Correct 85 ms 36176 KB Output is correct
8 Correct 63 ms 35020 KB Output is correct
9 Correct 62 ms 33744 KB Output is correct
10 Incorrect 59 ms 31072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19800 KB Output is correct
2 Correct 4 ms 19548 KB Output is correct
3 Correct 5 ms 19548 KB Output is correct
4 Correct 5 ms 19544 KB Output is correct
5 Correct 5 ms 19548 KB Output is correct
6 Correct 4 ms 19548 KB Output is correct
7 Correct 4 ms 19548 KB Output is correct
8 Correct 5 ms 19544 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19612 KB Output is correct
11 Correct 4 ms 19544 KB Output is correct
12 Correct 5 ms 19804 KB Output is correct
13 Correct 4 ms 19804 KB Output is correct
14 Correct 4 ms 19804 KB Output is correct
15 Correct 4 ms 19804 KB Output is correct
16 Incorrect 5 ms 19784 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31056 KB Output is correct
2 Correct 57 ms 31312 KB Output is correct
3 Correct 61 ms 30288 KB Output is correct
4 Correct 60 ms 29020 KB Output is correct
5 Correct 55 ms 27708 KB Output is correct
6 Correct 48 ms 26948 KB Output is correct
7 Correct 57 ms 26784 KB Output is correct
8 Correct 43 ms 26192 KB Output is correct
9 Correct 41 ms 26196 KB Output is correct
10 Correct 46 ms 25936 KB Output is correct
11 Correct 38 ms 25932 KB Output is correct
12 Correct 39 ms 25948 KB Output is correct
13 Correct 40 ms 25940 KB Output is correct
14 Correct 41 ms 28624 KB Output is correct
15 Correct 70 ms 35768 KB Output is correct
16 Correct 64 ms 33924 KB Output is correct
17 Correct 69 ms 34508 KB Output is correct
18 Correct 84 ms 32820 KB Output is correct
19 Incorrect 58 ms 29196 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19544 KB Output isn't correct
2 Halted 0 ms 0 KB -