Submission #639806

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
639806	2022-09-11 18:14:55	milisav	Valley (BOI19_valley)	C++14	100 / 100	300 ms	88688 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>
        using namespace std;
        #define endl '\n'
        #define int long long
         
        const int M = 3e5+5;
        int d[M], up[M][40], dp[M], mn[M][40], pr[M], ok[M], dist[M];
        vector<array<int, 3>> node[M];
        pair<int, int> v[M];
         
        void dfs(int s, int p, int dd = 0, int D = 0) {
            d[s] = D;
            dist[s] = dd;
            up[s][0] = p;
            dp[s] = (!ok[s])*LLONG_MAX;
            for (auto [i, w, x]:node[s]) {
                if (i != p) {
                    if (v[x].first != s) swap(v[x].first, v[x].second);
         
                    dfs(i, s, dd+w, D+1);
                    dp[s] = min(dp[s], dp[i]+w*(dp[i]!=LLONG_MAX));
                }
            }
         
            pr[s] = dp[s]-dd*(dp[s]!=LLONG_MAX);
        }
         
        int lca(int a, int b) {
            if (d[a] < d[b]) swap(a, b);
            for (int i = 0; i <= 20; i++) if ((d[a]-d[b])&(1<<i)) a = up[a][i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
valley.cpp:16:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |             for (auto [i, w, x]:node[s]) {
      |                       ^

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