Submission #112629

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
112629	2019-05-21 05:44:06	maruii	Factories (JOI14_factories)	C++14	100 / 100	3861 ms	110336 KiB

factories

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
const ll INF = 1e15;
int dfn[500005], dfnn, efn[500005], prt[19][500005];
int dep[500005];
ll D[500005];
vector<pii> edge[500005];
void dfs0(int x, int p) {
  dfn[x] = ++dfnn;
  for (auto i : edge[x]) {
    if (i.ss == p) continue;
    dep[dfnn + 1] = dep[dfn[x]] + 1;
    D[dfnn + 1] = D[dfn[x]] + i.ff;
    prt[0][dfnn + 1] = dfn[x];
    dfs0(i.ss, x);
  }
  efn[dfn[x]] = dfnn;
}
int C[1000005], cnt, pv, XY[500005];
ll res;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

factories.cpp: In function 'int lca(int, int)':
factories.cpp:49:15: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   if ((dep[s] - dep[e] >> i) & 1) s = prt[i][s];
        ~~~~~~~^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67