10.8校内膜你赛

T1.http://ezoj.org.cn/problem/382

第一眼是个单源最短路，不过直接建图的复杂度是m^2，明显不符合要求。

考虑给每个集合新建一个虚点，向集合内所有点连双向边（但只有一条有权值），复杂度O(nlgm)，期望得分100。

//两岸
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring> 
#define ll long long
#define FN "way"
#define inf 824602269000
using namespace std;
inline void Open()
{
    freopen(FN".in","r",stdin);
    freopen(FN".out","w",stdout); 
}
inline ll read()
{
    bool f=1;ll s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return f?s:-s;
}
priority_queue<pair <ll,ll> >q;
ll b[100010],n,m,t,s,cnt,ct,head[100010],dis[100010];
bool vis[100010]; 
struct Node
{
    ll to,nxt,val;
}a[200010];
inline void add(ll from,ll to,ll val)
{
    a[++cnt].to=to;
    a[cnt].val=val;
    a[cnt].nxt=head[from];
    head[from]=cnt;
}
int main()
{
    //Open(); 
    n=read(),m=read();ct=n;
    for(int i=1;i<=m;i++)
    {
        int t=read();ct++;
        for(int j=1;j<=t;j++)b[j]=read();
        ll x=read();
        for(int j=1;j<=t;j++)add(b[j],ct,0),add(ct,b[j],x);
    }
    s=read(),t=read();
    for(int i=1;i<=ct;i++){dis[i]=inf;vis[i]=0;}
    q.push(make_pair(0,s));dis[s]=0;
    while(!q.empty())
    {
        ll x=q.top().second;
        q.pop();
        if(vis[x])continue;vis[x]++;
        for(int i=head[x];i;i=a[i].nxt)
        {
            ll y=a[i].to;
            if(dis[y]>dis[x]+a[i].val)dis[y]=dis[x]+a[i].val,q.push(make_pair(-dis[y],y));
        }
    }
    if(dis[t]==inf)dis[t]=-1;
    printf("%lld",dis[t]);
    return 0;
}

zyb告诉我们优化建图可以做到nlgq+m，但是这和我们有什么关系呢？

T2.http://ezoj.org.cn/problem/383

不难发现（其实很难）对于所有可以构成直径的点都可以被分为两个集合，从每个集合任取两个点之间的路径都是树的直径，那么我们每次维护这个这两个集合就可以在时限内完成维护操作。

//两岸 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector> 
#define ll long long
#define FN "lct"
using namespace std;
inline void Open()
{
    freopen(FN".in","r",stdin);
    freopen(FN".out","w",stdout); 
}
ll lg[500010],n,cnt=0,mx=0;
vector<ll>s1,s2;
struct Poi
{
    ll dep,fa[100];
}d[500010];
inline ll read()
{
    bool f=1;ll s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return f?s:-s;    
} 
void build(ll x,ll fa)
{
    d[x].fa[0]=fa,d[x].dep=d[fa].dep+1;
    for(ll i=1;(1<<i)<=d[x].dep;i++)d[x].fa[i]=d[d[x].fa[i-1]].fa[i-1];
}
inline ll lca(ll x,ll y)
{
    ll ans=0;
    if(d[x].dep<d[y].dep)swap(x,y);
    while(d[x].dep>d[y].dep)ans+=1<<(lg[d[x].dep-d[y].dep]-1),x=d[x].fa[lg[d[x].dep-d[y].dep]-1];
    if(x==y)return ans;
    for(ll i=lg[d[x].dep]-1;i>=0;i--)
        if(d[x].fa[i]!=d[y].fa[i])ans+=1<<(i+1),x=d[x].fa[i],y=d[y].fa[i];
    return ans+2;    
}
int main()
{
    //Open();
    n=read()+1;lg[1]=1;
    s1.push_back(1);d[1].fa[0]=0;d[1].dep=1;
    for(ll i=2;i<=n;i++)
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        ll x=read();build(i,x);
        ll lc1=s1.empty()?0:lca(s1[0],i),lc2=s2.empty()?0:lca(s2[0],i);
        if(max(lc1,lc2)>mx)
        {
            mx=max(lc1,lc2);
            if(lc1==mx){for(ll j=0;j<s2.size();j++)if(lca(s2[j],i)==mx)s1.push_back(s2[j]);s2.clear();}
            else       {for(ll j=0;j<s1.size();j++)if(lca(s1[j],i)==mx)s2.push_back(s1[j]);s1.clear();}
        }
        if(max(lc1,lc2)==mx)(lc1==mx?s2:s1).push_back(i);
        printf("%d\n",s1.size()+s2.size());
    }
    return 0;
}

zyb告诉我们莽上lct可以过此题，但是这和我们有什么关系呢？

T3.http://ezoj.org.cn/problem/384

还没补……咕咕……

10.8校内膜你赛

相关推荐