Submission #899591

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
899591	2024-01-06 13:56:57	Mohammadamin__Sh	Valley (BOI19_valley)	C++17	100 / 100	195 ms	55228 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
//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x << endl
#define all(x) x.begin() , x.end()
const int maxn = 1e5 + 10, MOD = 1e9 + 7 , Lg = 22;
const ll INF = 1e18 + 100;
int n , s , q , root , par[maxn][Lg] , mini[maxn][Lg] , st[maxn] , fn[maxn] , t , val[maxn];
vector<pii> adj[maxn] , edge;
bool shop[maxn];
void Dfs(int v = root , int p = 0){
    par[v][1] = p , st[v] = ++t , par[v][0] = v;
    for(int i = 2 ; i < Lg ; i++) par[v][i] = par[par[v][i-1]][i-1] , mini[v][i] = INF;
    mini[v][0] = mini[v][1] = INF;
    for(pii u : adj[v]){
        if(u.S == p) continue;
        val[u.S] = val[v] + u.F;
        Dfs(u.S , v);
        mini[v][0] = min(mini[v][0] , mini[u.S][0] + u.F);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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