Submission #921894

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
921894	2024-02-04 13:03:45	falaz	Factories (JOI14_factories)	C++17	100 / 100	5819 ms	293220 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;
const int M = 5e5 + 1;
int st[M], fn[M], t, cnt, n , loc[M], ql, qr, lg[2 * M];
vector<pair<int, long long>> adj[M];
long long dis[M], seg[2][M << 2];
pair<int, int> par[20][M << 1];
void dfs(int v, int p, long long d1, int h) {
  dis[v] = d1;
  st[v] = t++;
  loc[v] = cnt;
  par[0][cnt++] = {h, v};
  for (auto u : adj[v]) 
    if (u.first != p) { 
      dfs(u.first, v, d1 + 1ll * u.second, h + 1);
      par[0][cnt++] = {h, v};
    }
  fn[v] = t - 1;
  return;
}
void update(int v, int l, int r, int i, long long k, bool g) {
  if (l == r) {
    seg[g][v] = k;
    return;
  }
  int mid = (r + l) >> 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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