Submission #1171410

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1171410	2025-03-21 00:51:21	aguss	Valley (BOI19_valley)	C++20	0 / 100	88 ms	24604 KiB

valley

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>
#define raya() cout << endl << "====================================" << endl
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbgv(v) cerr << #v << ": "; for(auto &el : v) cerr << el << " "; cerr << '\n';
#define INFINITY 1e8
using namespace std;
using ll = long long;
int n, s, q, e;
int lg = 5;
vector<vector<pair<int, int>>> arr;
vector<vector<int>> up, min_shop;
vector<int> dp, depth, distances;
unordered_set<int> shops;
int lca(int a, int b);
int calc_distance(int a, int b){
    return distances[a] + distances[b] - 2 * distances[lca(a, b)];
}
void dfs_min_shop(int curr, int prev, int weight){
    min_shop[curr][0] = min(dp[curr], dp[prev] + weight);
    for(int i = 1; i <= lg; i++){
        min_shop[curr][i] = min({
            min_shop[up[curr][i - 1]][i - 1] + calc_distance(curr, up[curr][i - 1]),
            min_shop[curr][i - 1]
        });
    }
    for(auto &x : arr[curr]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

valley.cpp:6: warning: "INFINITY" redefined
    6 | #define INFINITY 1e8
      | 
In file included from /usr/include/c++/11/cmath:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from valley.cpp:1:
/usr/include/math.h:91: note: this is the location of the previous definition
   91 | #  define INFINITY (__builtin_inff ())
      |

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41