oj.uz

Submission #396655

# Submission time Handle Problem Language Result Execution time Memory
396655 2021-04-30T14:18:54 Z AriaH Duathlon (APIO18_duathlon) C++11
23 / 100
 179 ms 73128 KB 
/** vaziat sorati ghermeze **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

ll tot;

int n, m, ts, H[N], Up[N], mark[N], sub[N];

vector < int > vec, G[N], adj[N];

void dfs(int v, int P = 0)
{
	Up[v] = H[v] = H[P] + 1;
	mark[v] = 1;
	for(auto u : G[v])
	{
		if(u == P) continue;
		if(mark[u])
		{
			Up[v] = min(Up[v], H[u]);
			continue;
		}
		int last = SZ(vec);
		dfs(u, v);
		if(Up[u] >= H[v])
		{
			ts ++;
			vec.push_back(v);
			while(SZ(vec) > last)
			{
				int node = vec.back();
				vec.pop_back();
				adj[ts].push_back(node);
				adj[node].push_back(ts);
				///printf("yal %d - %d\n", ts, node);
			}
		}
		Up[v] = min(Up[v], Up[u]);
	}
	vec.push_back(v);
}

void pre(int v, int P = 0)
{
	mark[v] = 1;
	sub[v] = (v <= n);
	for(auto u : adj[v])
	{
		if(u == P) continue;
		pre(u, v);
		sub[v] += sub[u];
	}
	///printf("v = %d sub = %d\n", v, sub[v]);
}

void calc(int v, int P, int _n)
{
	if(v <= n)
	{
		for(auto u : adj[v])
		{
			if(u == P) continue;
			calc(u, v, _n);
		}
		return;
	}
	ll p2 = 0;
	for(auto u : adj[v])
	{
		int cu = 0;
		if(u == P)
		{
			cu = _n - sub[v];
		}
		else
		{
			cu = sub[u];
		}
		///printf("v = %d u = %d cu = %d\n", v, u, cu);
		p2 += 1ll * cu *cu;
	}
	///printf("v = %d p2 = %lld\n", v, p2);
	for(auto u : adj[v])
	{
		int cu = 0;
		if(u == P)
		{
			cu = _n - sub[v];
		}
		else
		{
			cu = sub[v];
		}
		tot += 1ll * (_n - cu) * (_n - cu) - p2 + 1ll * cu * cu;
		tot += 1ll * (cu - 1) * (_n - cu);
	}
	for(auto u : adj[v]) 
	{
		if(u == P) continue;
		calc(u, v, _n);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	ts = n;
	for(int i = 1; i <= m; i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			dfs(i);
		}
	}
	memset(mark, 0, sizeof mark);
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			pre(i);
			calc(i, 0, sub[i]);
		}
	}
	printf("%lld", tot);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 51336 KB Output is correct
2 Correct 29 ms 51224 KB Output is correct
3 Correct 28 ms 51272 KB Output is correct
4 Correct 27 ms 51420 KB Output is correct
5 Correct 28 ms 51376 KB Output is correct
6 Correct 27 ms 51380 KB Output is correct
7 Correct 28 ms 51400 KB Output is correct
8 Correct 27 ms 51324 KB Output is correct
9 Correct 27 ms 51248 KB Output is correct
10 Correct 27 ms 51276 KB Output is correct
11 Correct 27 ms 51412 KB Output is correct
12 Correct 29 ms 51244 KB Output is correct
13 Correct 29 ms 51332 KB Output is correct
14 Correct 27 ms 51276 KB Output is correct
15 Correct 28 ms 51312 KB Output is correct
16 Correct 27 ms 51200 KB Output is correct
17 Correct 28 ms 51276 KB Output is correct
18 Correct 28 ms 51312 KB Output is correct
19 Correct 27 ms 51276 KB Output is correct
20 Correct 29 ms 51280 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 63556 KB Output is correct
2 Correct 136 ms 63680 KB Output is correct
3 Correct 144 ms 63524 KB Output is correct
4 Correct 129 ms 63544 KB Output is correct
5 Correct 128 ms 63504 KB Output is correct
6 Correct 148 ms 72004 KB Output is correct
7 Correct 179 ms 68984 KB Output is correct
8 Correct 141 ms 67652 KB Output is correct
9 Correct 147 ms 66128 KB Output is correct
10 Correct 145 ms 63616 KB Output is correct
11 Correct 152 ms 63572 KB Output is correct
12 Correct 142 ms 63684 KB Output is correct
13 Correct 131 ms 63536 KB Output is correct
14 Correct 138 ms 63008 KB Output is correct
15 Correct 117 ms 62212 KB Output is correct
16 Correct 81 ms 59584 KB Output is correct
17 Correct 116 ms 64196 KB Output is correct
18 Correct 101 ms 64140 KB Output is correct
19 Correct 101 ms 64244 KB Output is correct
20 Correct 106 ms 64160 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 51416 KB Output is correct
2 Correct 29 ms 51248 KB Output is correct
3 Incorrect 29 ms 51324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 63580 KB Output is correct
2 Correct 139 ms 63520 KB Output is correct
3 Incorrect 147 ms 63168 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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