Submission #7007

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
7007	2014-07-12 09:27:09	ainta	Factories (JOI14_factories)	C++98	100 / 100	5376 ms	117588 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<algorithm>
#define INF 999999999999999LL
using namespace std;
int Nxt[1000100], ed[1000100], L[1000100], P[500010];
int par[19][500010], num[500010], cnt, ran[500010], Dep[500010];
long long D[500010];
void DFS(int a, int pp){
  num[a] = ++cnt;
  int i;
  for (i = P[a]; i; i = Nxt[i]){
    if (pp != ed[i]){
      par[0][cnt + 1] = num[a];
      Dep[cnt + 1] = Dep[num[a]] + 1;
      D[cnt + 1] = D[num[a]] + L[i];
      DFS(ed[i], a);
    }
  }
  ran[num[a]] = cnt;
}
int LCA(int a, int b){
  if (Dep[a] < Dep[b])swap(a, b);
  int d = Dep[a] - Dep[b], c = 0;
  while (d){
    if (d & 1){
      a = par[c][a];
    }
    c++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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