Submission #1170416

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1170416	2025-03-19 19:58:21	DanerZein	Valley (BOI19_valley)	C++20	23 / 100	222 ms	75356 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; 
typedef long long ll; 
ll N,S,Q,E,a,b,c; 
vector<vector<pair<ll,ll>>> graph; 
vector<pair<ll,ll>> lista; 
vector<ll> alt,dp; 
vector<vector<ll>> padre,dist,resp; 
vector<bool> shop; 
ll dfs(int now,int ante){ 
    for(int i=1;i<20;i++){ 
        padre[now][i]=padre[padre[now][i-1]][i-1]; 
        dist[now][i]=dist[now][i-1]+dist[padre[now][i-1]][i-1]; 
    } 
    if(shop[now]){ 
        dp[now]=0; 
    } 
    for(auto u:graph[now]){ 
        if(u.first==ante){ 
            continue; 
        } 
        alt[u.first]=alt[now]+1; 
        padre[u.first][0]=now; 
        dist[u.first][0]=u.second; 
        dp[now]=min(dp[now],dfs(u.first,now)+u.second); 
    } 
    return dp[now]; 
} 
void calc(int now,int ante){ 
    resp[now][0]=dp[padre[now][0]]+dist[now][0]; 
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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