?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
230454777 |
Practice: racccccoon |
1468M - 32 | C++14 (GCC 6-32) | Accepted | 498 ms | 237384 KB | 2023-10-30 09:57:35 | 2023-10-30 09:57:35 |
// LUOGU_RID: 132428988 #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define mkp(x,y) make_pair((x),(y)) #define fir first #define sec second const int N=1e5+10; int n,B; vector<int>s[N]; int buc[N*2]; vector<pii>p[N*2]; int brr[N*2],len; void work() { scanf("%d",&n);B=0;len=0; for(int i=1;i<=n;i++) { int j;scanf("%d",&j); B+=j; while(j--) { int x;scanf("%d",&x); s[i].push_back(x);brr[++len]=x; } } B=sqrt(B)/2; // B=0; sort(brr+1,brr+len+1);len=unique(brr+1,brr+len+1)-brr-1; for(int i=1;i<=n;i++) { for(auto &x:s[i]) x=lower_bound(brr+1,brr+len+1,x)-brr; } pii ans=mkp(0,0); for(int i=1;i<=n;i++) { if((int)s[i].size()<=B)continue; for(auto x:s[i])buc[x]=1; for(int j=1;j<=n;j++) { if(j==i)continue; bool cnt=0; for(auto y:s[j]) { if(buc[y]) cnt?ans=mkp(i,j),1:cnt=1; } } for(auto x:s[i])buc[x]=0; if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void(); } for(int i=1;i<=n;i++) { if((int)s[i].size()>B)continue; for(int j=0;j<s[i].size();j++) { for(int k=j+1;k<s[i].size();k++) { p[min(s[i][j],s[i][k])].push_back(mkp(max(s[i][k],s[i][j]),i)); } } } for(int i=1;i<=len;i++) { for(auto x:p[i]) buc[x.fir]?ans=mkp(buc[x.fir],x.sec),1:buc[x.fir]=x.second; for(auto x:p[i]) buc[x.fir]=0; if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void(); } return puts("-1"),void(); } void clear() { for(int i=1;i<=n;i++) s[i].clear(); for(int i=1;i<=len;i++) p[i].clear(); } int main() { int T;scanf("%d",&T); while(T--)work(),clear(); return 0; }
?
?
?
?