Submission #754803

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
754803	2023-06-08 15:08:20	Desh03	Factories (JOI14_factories)	C++17	100 / 100	5103 ms	171520 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 <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
vector<long long> d, mn;
vector<int> dep, out, sz, par, euler;
vector<bool> centroid;
vector<vector<pair<int, int>>> g;
void dfs(int u, int p) {
    out[u] = euler.size();
    euler.push_back(u);
    for (auto [v, w] : g[u])
        if (v ^ p) {
            d[v] = d[u] + w;
            dep[v] = dep[u] + 1;
            dfs(v, u);
            out[u] = euler.size();
            euler.push_back(u);
        }
}
struct RMQ {
    vector<vector<int>> sparse;
    vector<int> lg;
    int comp(const int &a, const int &b) {
        return dep[a] < dep[b] ? a : b;
    }
    void init(const vector<int> &v) {
        int n = v.size();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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