Submission #950115

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
950115	2024-03-20 05:32:15	Abdalaziz_Alshami	Two Currencies (JOI23_currencies)	C++17	28 / 100	464 ms	51152 KiB

currencies

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 int long long
using namespace std;
const int N=1e5+5,lo=21;
int an[N][lo],dis[N],cost[N];
map<pair<int,int>,int>mp;
pair<int,int> ed[N];
vector<int> a[N];
void dfs(int x,int p)
{
    an[x][0]=p;
    dis[x]=dis[p]+1;
    cost[x]=mp[{x,p}]+cost[p];
    for(int i=1;i<lo;i++) an[x][i]=an[an[x][i-1]][i-1];
    for(auto i:a[x]) if(i!=p) dfs(i,x);
}
int lca(int x,int y)
{
    if(dis[x]>dis[y]) swap(x,y);
    for(int i=lo-1;i>=0;i--)
        if(dis[an[y][i]]>=dis[x]) y=an[y][i];
    if(x==y) return x;
    for(int i=lo-1;i>=0;i--)
        if(an[x][i]!=an[y][i])
            x=an[x][i],y=an[y][i];
    return an[x][0];
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 10
• Subtask 2: 28 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32