Submission #850874

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
850874	2023-09-17 15:35:12	annabeth9680	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	32 ms	10584 KiB

roadsideadverts

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 f first
#define s second
using namespace std;
const int MAXN = 5e4+11;
vector<pair<int,int>> adj[MAXN];
int tin[MAXN], tout[MAXN], par[MAXN][20], dep[MAXN], dist[MAXN];
int timer;
void dfs(int u, int p){
    tin[u] = ++timer;
    for(auto c : adj[u]){
        if(c.f != p){
            dep[c.f] = dep[u]+1; par[c.f][0] = u; dist[c.f] = dist[u]+c.s;
            dfs(c.f,u);
        }
    }
    tout[u] = timer;
}
int calcanc(int u, int k){
    for(int i = 19;i>=0;--i){
        if(k >= (1<<i)){
            u = par[u][i];
            k -= (1<<i);
        }
    }
    return u;
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u,v);
    u = calcanc(u,dep[u]-dep[v]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30