Submission #921892

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
921892	2024-02-04 12:57:42	falaz	Factories (JOI14_factories)	C++17	100 / 100	3870 ms	301168 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 , TV = 1, 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 i, long long k, bool g) {
  i = i + TV;
  seg[g][i] = k;
  i /= 2;
  while (i) {
    seg[g][i] = min(seg[g][i << 1], seg[g][i << 1 | 1]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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