oj.uz

Submission #958535

# Submission time Handle Problem Language Result Execution time Memory
958535 2024-04-06T01:48:36 Z Cyber_Wolf Duathlon (APIO18_duathlon) C++17
0 / 100
 82 ms 40392 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;
	for(auto it : adj2[src])
	{
		if(vis[it])	continue;
		dfs2(it);
		sz[src] += sz[it];
		if(src > n)
		{
			ans -= sz[it]*(sz[it]-1)*adj2[src].size();
		}
	}
	if(src > n)
	{
		ans -= (n2-sz[src])*(n2-sz[src]-1)*adj2[src].size();
	}
}

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 19548 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 19548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 36936 KB Output is correct
2 Correct 48 ms 36928 KB Output is correct
3 Incorrect 60 ms 34128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31144 KB Output is correct
2 Correct 59 ms 32340 KB Output is correct
3 Correct 57 ms 32340 KB Output is correct
4 Correct 59 ms 32336 KB Output is correct
5 Correct 58 ms 32340 KB Output is correct
6 Correct 65 ms 40392 KB Output is correct
7 Correct 66 ms 37524 KB Output is correct
8 Correct 74 ms 36300 KB Output is correct
9 Correct 65 ms 34972 KB Output is correct
10 Incorrect 56 ms 32336 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 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 5 ms 19800 KB Output is correct
4 Correct 5 ms 19660 KB Output is correct
5 Correct 5 ms 19548 KB Output is correct
6 Correct 5 ms 19548 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19672 KB Output is correct
10 Correct 4 ms 19548 KB Output is correct
11 Correct 5 ms 19548 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 4 ms 19804 KB Output is correct
14 Correct 6 ms 19804 KB Output is correct
15 Correct 5 ms 19800 KB Output is correct
16 Incorrect 5 ms 20052 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31100 KB Output is correct
2 Correct 62 ms 32600 KB Output is correct
3 Correct 60 ms 31780 KB Output is correct
4 Correct 79 ms 30504 KB Output is correct
5 Correct 66 ms 29084 KB Output is correct
6 Correct 47 ms 28384 KB Output is correct
7 Correct 48 ms 28156 KB Output is correct
8 Correct 49 ms 27492 KB Output is correct
9 Correct 41 ms 27484 KB Output is correct
10 Correct 42 ms 27404 KB Output is correct
11 Correct 48 ms 27216 KB Output is correct
12 Correct 39 ms 26972 KB Output is correct
13 Correct 39 ms 27216 KB Output is correct
14 Correct 42 ms 29944 KB Output is correct
15 Correct 82 ms 37064 KB Output is correct
16 Correct 69 ms 35352 KB Output is correct
17 Correct 69 ms 36036 KB Output is correct
18 Correct 76 ms 34252 KB Output is correct
19 Incorrect 59 ms 30536 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 19548 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 19548 KB Output isn't correct
2 Halted 0 ms 0 KB -