The title says its all!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | adamant | 155 |
7 | nor | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 148 |
The title says its all!
Hi!
Recently I tried to solve a problem with 1.5s time limit. After several tries, I finally got AC within 1496ms.
Share your lucky moments!!!
Hi all!
Recently, I tried to implement a HLD struct. However, my local computer shows Segmentation Fault verdict as soon as I set the constraint of N to 1e5, the online judge shows TLE verdict btw. Small constraint on N works just fine. Here is the code:
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
template<typename seg_t>
struct HLD{
int P[N][20];
int parent[N];
int depth[N];
int child[N];
int bigChild[N];
int chain[N];
seg_t arr[N];
seg_t tree[3 * N];
int label[N];
int label_time = 0;
vector<int> g[N];
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
seg_t get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init(int root){
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0; i <= n; i++){
parent[i] = -1;
chain[i] = i;
}
parent[root] = root;
dfs(root, 0);
buildLCA();
dfs_labels(arr, 1, -1);
}
void dfs(int u, int level){
depth[u] = level;
child[u] = 1;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(parent[x] == -1){
parent[x] = u;
dfs(x, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigc = x;
bigv = child[x];
}
}
}
bigChild[u] = bigc;
}
void buildLCA(){
for(int i = 0; i <= n; i++){
for(int j = 1; j <= trunc(log2(n)); j++)
P[i][j] = -1;
}
for(int i = 1; i <= n; i++)
P[i][0] = parent[i];
for(int j = 1; j <= trunc(log2(n)); j++)
for(int i = 0; i <= n; i++)
if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int x = 1;
while(x <= log2(depth[u])) x++;
x--;
for(int i = x; i >= 0; i--)
if(depth[u] - (1<<i) >= depth[v]) u = P[u][i];
if(u == v) return u;
for(int i = x; i >= 0; i--)
if(P[u][i] != -1 && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
return parent[u];
}
int k_th_ancestor(int u, int k){
if(k == 0) return u;
int cur = u;
for(int i = 17; i >= 0; i--){
if(k >= pow(2, i)){
k -= pow(2, i);
cur = P[cur][i];
}
}
return cur;
}
void dfs_labels(seg_t* a, int u, int v){
label[u] = label_time++;
update(1, 0, n - 1, label[u], a[u]);
if(bigChild[u] != -1) dfs_labels(a, bigChild[u], u);
for(auto x: g[u]){
if(x != v && x != bigChild[u])
dfs_labels(a, x, u);
}
}
void dfs_chains(int u, int v){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == v) continue;
dfs_chains(x, u);
}
}
seg_t query_chain(int u, int p){
seg_t res = 0;
while(depth[p] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[p]){
int diff = depth[u] - depth[p];
top = k_th_ancestor(u, diff - 1);
}
res = res ^ get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
seg_t query(int u, int v){
int anc = lca(u, v);
seg_t res = query_chain(u, anc) ^ query_chain(v, anc);
res ^= get(1, 0, n - 1, label[anc], label[anc]);
return res;
}
};
void Solve(){
int q;
cin>>n>>q;
HLD<int> h;
for(int i = 1; i <= n; i++)
cin>>h.arr[i];
h.init(1);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) h.update(1, 0, n - 1, h.label[x], y);
else cout<<h.query(x, y)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
So, I tried to rewrite the same code without using struct. This time my local computer ran smoothly and the online judge showed AC verdict.
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
vector<int> g[N];
int arr[N];
int bigChild[N];
int child[N];
int depth[N];
int chain[N];
int label[N], label_time;
int parent[N];
int lca_lift[N][20];
int tree[3 * N];
int k_th_ancestor(int u, int k);
void lca_dfs(int u, int p);
void dfs_size(int u, int p, int level);
void dfs_chains(int u, int p);
void dfs_labels(int u, int p);
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
int get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init_arrays(){
for(int i = 0; i < N; i++)
chain[i] = i;
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
}
void addEdge(int u, int v){
g[u].push_back(v);
g[v].push_back(u);
}
void initTree(int root){
lca_dfs(root, -1);
dfs_size(root, -1, 0);
dfs_chains(root, -1);
label_time = 0;
dfs_labels(root, -1);
}
void lca_dfs(int u, int p){
lca_lift[u][0] = p;
for(int i = 1; i < 20; i++){
if(lca_lift[u][i - 1] == -1) lca_lift[u][i] = -1;
else lca_lift[u][i] = lca_lift[lca_lift[u][i - 1]][i - 1];
}
for(auto x: g[u])
if(x != p) lca_dfs(x, u);
}
void dfs_size(int u, int p, int level){
child[u] = 1;
depth[u] = level;
parent[u] = p;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(x == p) continue;
dfs_size(x, u, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigv = child[x];
bigc = x;
}
}
bigChild[u] = bigc;
}
void dfs_chains(int u, int p){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == p) continue;
dfs_chains(x, u);
}
}
void dfs_labels(int u, int p){
label[u] = label_time++;
update(1, 0, n - 1, label[u], arr[u]);
if(bigChild[u] != -1) dfs_labels(bigChild[u], u);
for(auto x: g[u]){
if(x == p || x == bigChild[u]) continue;
dfs_labels(x, u);
}
}
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
int u = k_th_ancestor(a, d);
if(u == b) return u;
for(int i = 19; i >= 0; i--){
if(lca_lift[u][i] != lca_lift[b][i]){
u = lca_lift[u][i];
b = lca_lift[b][i];
}
}
return lca_lift[b][0];
}
int k_th_ancestor(int u, int k){
for(int i = 19; i >= 0; i--){
if(u == -1) return u;
if((1 << i) <= k){
u = lca_lift[u][i];
k -= (1 << i);
}
}
return u;
}
int query_chain(int u, int v){
int res = 0;
while(depth[v] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[v]){
int diff = depth[u] - depth[v];
top = k_th_ancestor(u, diff - 1);
}
res ^= get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
int query(int u, int v){
int anc = lca(u, v);
int res = query_chain(u, anc) ^ query_chain(v, anc);
return res ^ get(1, 0, n - 1, label[anc], label[anc]);
}
void Solve(){
int q;
cin>>n>>q;
for(int i = 0; i < n; i++)
cin>>arr[i];
init_arrays();
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
u--; v--;
addEdge(u, v);
}
initTree(0);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) update(1, 0, n - 1, label[x - 1], y);
else cout<<query(x - 1, y - 1)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
Could someone plz explain why's there a difference verdict in my codes? Where did I get it wrong? I much appreciate it!
Most of the editorials are well-written in a very formal way. I guess I'm not good at reading formal stuff. Luckily, I have my own solution for this, reading contest announcement comments or looking at jiangly submissions. Not gonna lie, his codes are super neat and thankfully he participates in most of the contests both officially and unofficially.
Name |
---|