XOR pairs#11774
Problem Author: | Pavlo Tsikalyshyn |
Prepared by: | Pavlo Tsikalyshyn |
Editorial by: | Pavlo Tsikalyshyn |
Firstly, let's learn how to solve the second block of test. In that block you have a chain, so we just go from 1 to a leaf and try to found a solution for the current node, if we have found one this will also be a solution for every node in the path to the leaf. Let's try to implement a solution with complexity O(n^2). So we will save for every number a vector of pair of indexes for which a_i \oplus a_j = . If for some we will have pairs, then we could find an answer. Because if pair looks like (x_0, x_1), (x_0, x_2), (x_0, x_3), (x_0, x_4) than answer will be x_1, x_2, x_3, x_4. If indexes in pairs repeat at most 3 times, then we have at most one such index x_0 which repeats times (x_0, x_1), (x_0, x_2), (x_0, x_3), (w, v), where x_0 is not equal to , so exists at least one x_i which is not equal to or , and answer than will be x_0, x_i, w, v. So to calculate answer for this block will take O(a_{max}) time.
To solve the whole problem you need to do DFS and when you come out of the node just remove pair which you have create in this node. In the worst case, you will have complexity O(n \sqrt{a_{max}}) as in a path of length 3 \cdot \sqrt{a_{max}} we approximately have \frac{9}{2} \cdot a_{max} pair of on the path, and then we will have such an for which we will have at least 4 pairs with the same xor x=a_i \oplus a_j and then the solution exists.
#include <iostream>
#include <vector>
using namespace std;
bool check(vector<vector<pair<int, int>>>& c, int x, pair<pair<int, int>, pair<int, int>>& res){
for(int i=0;i<c[x].size()-1;++i){
if(c[x][i].first != c[x].back().first and c[x][i].first != c[x].back().second and c[x][i].second != c[x].back().first and c[x][i].second != c[x].back().second){
res = {c[x][i], c[x].back()};
return true;
}
}
if(c[x].size() != 4) return false;
int same;
if(c[x][0].first != c[x][1].first and c[x][0].first != c[x][1].second){
same = c[x][0].second;
res.first.first = c[x][0].first;
}else{
same = c[x][0].first;
res.first.first = c[x][0].second;
}
if(same == c[x][1].first){
res.first.second = c[x][1].second;
}else{
res.first.second = c[x][1].first;
}
if(same == c[x][2].first){
res.second.first = c[x][2].second;
}else{
res.second.first = c[x][2].first;
}
if(same == c[x][3].first){
res.second.second = c[x][3].second;
}else{
res.second.second = c[x][3].first;
}
return true;
}
void DFS(int id, int last, vector<int>& a, vector<vector<int>>& b, vector<vector<pair<int, int>>>& c, pair<pair<int, int>, pair<int, int>> res, vector<pair<pair<int, int>, pair<int, int>>>& ans, vector<int>& d){
if(res.first.first != -1){
ans[id] = res;
for(auto el: b[id]){
if(el == last) continue;
DFS(el, id, a, b, c, res, ans, d);
}
}else{
int i;
for(i=0;i<d.size();++i){
c[a[d[i]]^a[id]].push_back({d[i], id});
if(check(c, a[d[i]]^a[id], res)){
ans[id] = res;
for(;i>=0;--i){
c[a[d[i]]^a[id]].pop_back();
}
break;
}
}
d.push_back(id);
for(auto el: b[id]){
if(el == last) continue;
DFS(el, id, a, b, c, res, ans, d);
}
d.pop_back();
if(i == d.size()){
for(--i;i>=0;--i){
c[a[d[i]]^a[id]].pop_back();
}
}
}
}
int main() {
int n, i, x, y;
cin>>n;
vector<int> a(n);
vector<vector<int>> b(n);
vector<vector<pair<int, int>>> c(1<<18);
vector<int> d;
pair<pair<int, int>, pair<int, int>> res;
res = {{-1, -1}, {-1, -1}};
vector<pair<pair<int, int>, pair<int, int>>> ans(n, res);
for(i=0;i<n;++i){
cin>>a[i];
}
for(i=1;i<n;++i){
cin>>x>>y;
--x;
--y;
b[x].push_back(y);
b[y].push_back(x);
}
DFS(0, -1, a, b, c, res, ans, d);
for(i=0;i<n;++i){
if(ans[i].first.first == -1){
cout<<"-1 -1 -1 -1"<<endl;
}else{
cout<<ans[i].first.first+1<<' '<<ans[i].first.second+1<<' '<<ans[i].second.first+1<<' '<<ans[i].second.second+1<<endl;
}
}
return 0;
}