Submission #828471

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
828471	2023-08-17 10:07:53	khshg	Two Currencies (JOI23_currencies)	C++14	100 / 100	829 ms	31200 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>
using namespace std;
#define pb push_back
int N, M, Q;
vector<vector<int>> adj;
vector<int> par, sz, anc, flat, pos;
vector<pair<int, int>> e, ch;
vector<int> S, T, X;
vector<long long> Y;
void dfs_sz(int s) {
  sz[s] = 1;
  if(adj[s][0] == par[s] && (int)adj[s].size() >= 2) swap(adj[s][0], adj[s][1]);
  for(auto& u : adj[s]) {
    if(u == par[s]) continue;
    par[u] = s;
    dfs_sz(u);
    sz[s] += sz[u];
    if(sz[adj[s][0]] < sz[u]) swap(adj[s][0], u);
  }
}
void build_hld(int s, int r) {
  pos[s] = (int)flat.size();
  flat.pb(s);
  anc[s] = r;
  for(auto& u : adj[s]) {
    if(u == par[s]) continue;
    build_hld(u, (u == adj[s][0] ? r : u));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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