Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
24250 fyq & jbh's LCA 【BJ】T3 C++ 运行出错 0 5 MS 8176 KB 1674 2023-12-20 21:57:25

Tests(0/20):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define p1 first #define p2 second #define pi pair<int,int> #define m_p make_pair #define x1 x114514 #define y1 y114514 using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxn=1e5+10,N=2e6,mod=1e9+7; inline int read(){ int x=0; short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,L[maxn],mn1[maxn],bel1[maxn],mn2[maxn],bel2[maxn],t[maxn]; vector<int>C[maxn],F[maxn],P[maxn]; int get_col(int x){ int res=0; up(i,1,L[x]){ if(!t[C[x][i]])t[C[x][i]]=1,P[x].p_b(C[x][i]),res++; }for(int y:P[x])t[y]=0; return res; } void slv(){ n=read(); int res=1e9; up(i,1,1e5)mn1[i]=mn2[i]=1e9; up(i,1,n){ L[i]=read();C[i].resize(L[i]+5),F[i].resize(L[i]+5); up(j,1,L[i])C[i][j]=read(); int ret=get_col(i); res=min(res,ret+1); for(int x:P[i]){ if(ret<mn1[x])mn2[x]=mn1[x],bel2[x]=bel1[x],mn1[x]=ret,bel1[x]=i; else if(ret<=mn2[x])mn2[x]=ret,bel2[x]=i; } }up(i,1,n){ int ll=0; for(int x:P[i]){ if(bel1[x]==i)F[i][++ll]=mn2[x]; else F[i][++ll]=mn1[x]; }sort(F[i].begin()+1,F[i].begin()+ll+1,greater<int>()); up(j,1,ll)res=min(res,F[i][j]+j); }cout<<res<<'\n'; } int main(){ // freopen("1.in","r",stdin); int t=read();while(t--)slv(); return 0; } /* Moyun & JBH */


测评信息: