Submission #393240

#	Time	Username	Problem	Language	Result	Execution time	Memory
393240		AriaH	Duathlon (APIO18_duathlon)	C++11	0 / 100	1128 ms	1048580 KiB

count_triplets

/** I can do this all day **/

#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 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);
#define endl                        "\n"

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 q, P[N], sub[N], sz[N], par[N], H[N];

ll n, tot, Ans[N]; /// Ans[v] -> tedad halate entekhabe 2 raas ke v vasateshoon bashe

vector < int > G[N];

void dfs(int v)
{
    H[v] = H[P[v]] + 1;
    sz[v] = sub[v] = 1;
    for(auto u : G[v])
    {
	if(u == P[v]) continue;
	P[u] = v;
	dfs(u);
	sub[v] += sub[u];
	Ans[v] += sub[u] * (n - sub[u] - 1);
    }
    Ans[v] += (n - sub[v]) * (sub[v] - 1);
    tot += Ans[v];
}

int get(int x) { return (x == par[x])? x : par[x] = get(par[x]); }

void unify(int v, int u)
{
    while(get(v) != get(u))
    {
	v = get(v), u = get(u);
	if(H[v] < H[u]) swap(u, v);
	ll p = get(P[v]), T = n - sub[v] - sz[p], S = sub[v] - sz[v];
	tot += sz[v] * sz[p] * (sz[v] + sz[p] - 2); /// 2 ras az v, yeki az p, 2 ras az p yeki az v
	tot += (n - sz[v] - sz[p]) * sz[v] * sz[p] * 2; /// yeki az v va p, yeki az kharej
	tot += (Ans[v] - 2 * (n - sub[v]) * S) * sz[p]; /// tedad halati ke ras haye p vasat bashan cheghad ezafe motamam roye onaii ke ezafe nemishan va hesab shode
	tot += (Ans[p] - 2 * sub[v] * T) * sz[v]; /// tedad halati ke ras haye v vasat bashan cheghad ezafe mishe mese ba motamam
	Ans[p] += Ans[v];
	Ans[p] -= 2 * (T * sz[v] + S * sz[p] + S * T); /// update kardane Ans[p] -> motamam roye tekrari ha
        sz[p] += sz[v];
        par[v] = p;
	v = p;
     }
}

int main()
{
	int m;
    scanf("%lld%d", &n, &m);
    for(int i = 1; i <= n; i ++) par[i] = i;
    for(int i = 1; i < n; i ++)
    {
	int a, b;
	scanf("%d%d", &a, &b);
	G[a].push_back(b);
	G[b].push_back(a);
    }
    dfs(1);
    q = m - n + 1;
	while(q--)
    {
	int v, u;
	scanf("%d%d", &v, &u);
	unify(v, u);
    }
	printf("%lld", tot);
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10