#pragma GCC optimize("Ofast,unroll-loops") #include #include #include #include #include using namespace std; typedef basic_string vi; #define all(x) begin(x),end(x) constexpr size_t N = 100000; constexpr size_t B = sqrt(N/32); constexpr size_t V = N/B; int main() { cin.tie(NULL); cin.sync_with_stdio(false); cerr << B << '\n'; int m; cin >> m; vector> A(m); for(int i=0;i> k; v.resize(k); for(auto& i : v) cin >> i, c.push_back(i); } sort(all(c)); c.erase(unique(all(c)),c.end()); // coordinate compression. for(auto& [v,id] : A) { for(auto& i : v) { i = lower_bound(all(c),i)-c.begin(); } sort(all(v)); } sort(all(A),[&](auto& i, auto& j) {return i.first.size()>j.first.size();}); int k = c.size(); vector> bs(k); // essentially bruteforce all pairs of sets, with first one being >=B, the other one: not care. // time complexity O(n^2/(B*32)) for(int i=0;i mine; for(int j : A[i].first) { if((mine & bs[j]).any()) { // j and some other element in set A_i share another set, so they are a good pair! int who = (mine&bs[j])._Find_first(); for(int other : A[i].first) if(bs[other][who]) { cout << c[j] << ' ' << c[other] << ' ' << A[i].second << ' ' << A[who].second << '\n'; exit(0); } } mine|=bs[j]; if(A[i].first.size()>=B) bs[j][i]=1; } } vector smallsets(k); for(int i=0;i vis(k); // boolean flag, but vector is bad. // these three for loops overall are O(n * B) time complexity. for(int j=0;j