Submission #930323

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
930323	2024-02-19 10:55:23	vjudge1	Factories (JOI14_factories)	C++17	100 / 100	3218 ms	275128 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 NM = 5e5 + 5;
const int LG = __lg(NM);
 
vector<pair<int, int>> adj[NM];
bool visited[NM];
vector<int> tour;
int depth[NM], tin[NM], tout[NM];
long long dist[NM];
pair<int, int> ST[LG + 2][NM << 1];
 
void dfs_euler_tour(const int &u) {
    visited[u] = 1;
 
    tin[u] = tour.size();
    tour.emplace_back(u);
 
    for (auto &[v, w]: adj[u])
        if (!visited[v]) {
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;
 
            dfs_euler_tour(v);
            tour.emplace_back(u);
        }
 
    tout[u] = tour.size() - 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

factories.cpp: In function 'void build_sparse_table()':
factories.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < tour.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j = 0; j + (1 << i) - 1 < tour.size(); ++j)
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 1; i < node.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

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