oj.uz

Submission #393240

# Submission time Handle Problem Language Result Execution time Memory
393240 2021-04-23T04:02:41 Z AriaH Duathlon (APIO18_duathlon) C++11
0 / 100
 1000 ms 1048580 KB 
/** 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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 670 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 670 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 38224 KB Output is correct
2 Correct 91 ms 37632 KB Output is correct
3 Execution timed out 1099 ms 439208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23920 KB Output is correct
2 Correct 14 ms 23880 KB Output is correct
3 Correct 14 ms 23832 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 14 ms 23928 KB Output is correct
6 Correct 14 ms 23872 KB Output is correct
7 Correct 14 ms 23884 KB Output is correct
8 Correct 14 ms 23932 KB Output is correct
9 Correct 14 ms 23884 KB Output is correct
10 Execution timed out 1094 ms 23904 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 33092 KB Output is correct
2 Correct 75 ms 32908 KB Output is correct
3 Correct 74 ms 32964 KB Output is correct
4 Correct 88 ms 32964 KB Output is correct
5 Correct 81 ms 32904 KB Output is correct
6 Correct 82 ms 37236 KB Output is correct
7 Correct 83 ms 35684 KB Output is correct
8 Correct 83 ms 34972 KB Output is correct
9 Correct 79 ms 34192 KB Output is correct
10 Execution timed out 1098 ms 32968 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23888 KB Output is correct
2 Correct 15 ms 23900 KB Output is correct
3 Execution timed out 1095 ms 23884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 32920 KB Output is correct
2 Correct 77 ms 32872 KB Output is correct
3 Execution timed out 1128 ms 888260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 670 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 670 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -