제출 #310856

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
310856	2020-10-08 08:50:45	vipghn2003	공장들 (JOI14_factories)	C++14	100 / 100	2607 ms	230920 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;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
const int maxN = 5e5 + 7;
int n, level[maxN], st[maxN], ed[maxN], cnt = 0, now = 0, sz = 0, euler[2 * maxN], lg[2 * maxN], ft[maxN];
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN], par[20][2 * maxN];
vector < pair <int, int> > edge[maxN];
 
void dfs(int u, int p){
  st[u] = ++cnt;
  euler[++now] = u;
  ft[u] = now;
  for(pair <int, int> to : edge[u]){
    int v = to.fi, w = to.se;
    if(v == p) continue;
    level[v] = level[u] + 1;
    depth[v] = depth[u] + w;
    dfs(v, u);
    euler[++now] = u;
  }
  ed[u] = cnt;
}
 
pair <int, int> get(int l, int r){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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