Submission #761242

#	Time	Username	Problem	Language	Result	Execution time	Memory
761242		bgnbvnbv	Phone Plans (CCO22_day2problem2)	C++14	0 / 25	335 ms	124232 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,a,b,k;
ll lab[maxN],val[maxN],sz[maxN],cnt=0;
void build()
{
    cnt=0;
    for(int i=1;i<=n+a+b;i++) lab[i]=-1,val[i]=0;
    for(int i=1;i<=n;i++) sz[i]=1;
}
struct Tedge
{
    ll u,v,w;
    bool operator<(const Tedge&o)
    {
        return w<o.w;
    }
}e[maxN],f[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
bool unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return false;
    if(lab[u]>lab[v]) swap(u,v);
    cnt-=val[u];
    cnt-=val[v];
    val[u]=val[u]+val[v]+sz[u]*sz[v];
    sz[u]+=sz[v];
    lab[u]+=lab[v];
    cnt+=val[u];
    lab[v]=u;
    return true;
}
vector<pli>g[maxN];
bool vis[maxN];
ll P[maxN][20],mx[maxN][20],h[maxN];
void dfs(ll u,ll p)
{
    P[u][0]=p;
    vis[u]=true;
    for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(int i=1;i<=18;i++) mx[u][i]=max(mx[u][i-1],mx[P[u][i-1]][i-1]);
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            h[vv.fi]=h[u]+1;
            mx[vv.fi][0]=vv.se;
            dfs(vv.fi,u);
        }
    }
}
ll lca(ll u,ll v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=18;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
    return P[u][0];
}
ll pth(ll u,ll v)
{
    ll k=h[u]-h[v];
    ll aa=0;
    for(int i=18;i>=0;i--)
    {
        if(k>>i&1)
        {
            aa=max(aa,mx[u][i]);
            u=P[u][i];
        }
    }
    return aa;
}
ll get(ll u,ll v)
{
    ll x=lca(u,v);
    if(x==0) return max(a,b)+1;
    return max(pth(u,x),pth(v,x));
}
struct qq
{
    ll t,id,w,u,v;
    bool operator<(const qq&o)
    {
        if(w==o.w) return t<o.t;
        return w<o.w;
    }
};
vector<qq>edge;
ll suma[maxN],sumb[maxN];
void solve()
{
    cin >> n >> a >> b >> k;
    build();
    for(int i=1;i<=a;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e+1,e+a+1);
    for(int i=1;i<=a;i++)
    {
        if(unite(e[i].u,e[i].v))
        {
            g[e[i].u].pb({e[i].v,i});
            g[e[i].v].pb({e[i].u,i});
        }
    }
    for(int i=1;i<=n;i++) vis[i]=false;
    h[0]=-1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            dfs(i,0);
        }
    }
    for(int i=1;i<=b;i++)
    {
        cin >> f[i].u >> f[i].v >> f[i].w;
    }
    sort(f+1,f+b+1);
    for(int i=1;i<=b;i++)
    {
        ll x=get(f[i].u,f[i].v);
        if(x>a) continue;
        edge.pb({0,i,f[i].w,f[i].u,n+i});
        edge.pb({0,x,e[x].w,n+i,f[i].v});
    }
    build();
    for(int i=1;i<=n;i++) g[i].clear();
    for(int i=1;i<=b;i++)
    {
        if(unite(f[i].u,f[i].v))
        {
            g[f[i].u].pb({f[i].v,i});
            g[f[i].v].pb({f[i].u,i});
        }
    }
    for(int i=1;i<=n;i++)
    {
        vis[i]=false,h[i]=0;
        for(int j=0;j<=18;j++) P[i][j]=0,mx[i][j]=0;
    }
    h[0]=-1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            dfs(i,0);
        }
    }

   // cout <<mx[2][0]<<' '<<get(2,6)<<'\n';
    for(int i=1;i<=a;i++)
    {
        ll x=get(e[i].u,e[i].v);
        if(x>b) continue;
        edge.pb({0,i,e[i].w,e[i].u,b+n+i});
        edge.pb({0,x,f[x].w,n+i+b,e[i].v});
        //cout << e[i].w<<' '<<f[x].w<<'\n';
    }
    for(int i=1;i<=a;i++) edge.pb({1,i,e[i].w,n,n});
    for(int i=1;i<=b;i++) edge.pb({2,i,f[i].w,n,n});
    sort(edge.begin(),edge.end());
    build();
    for(int i=1;i<=a;i++)
    {
        unite(e[i].u,e[i].v);
        suma[i]=cnt;
        //cout << suma[i]<< ' ';
    }
    build();
    for(int i=1;i<=b;i++)
    {
        unite(f[i].u,f[i].v);
        sumb[i]=cnt;
        //cout<< sumb[i]<<' ';
    }
    build();
    ll id1=0,id2=0;
    ll ans=-1;
    ll kind;
    for(int i=0;i<edge.size();i++)
    {
        unite(edge[i].u,edge[i].v);
        if(edge[i].t==2)
        {
            id2=edge[i].id;
        }
        else if(edge[i].t==1)
        {
            id1=edge[i].id;
        }
        if(suma[id1]+sumb[id2]-cnt>=k)
        {
            ans=edge[i].w;
            kind=edge[i].t;
            break;
        }
    }
    if(ans==-1)
    {
        cout << ans;
        return;
    }
    build();
    id1=0,id2=0;
    for(int i=0;i<edge.size();i++)
    {
        if(edge[i].t==kind)
        {
            unite(edge[i].u,edge[i].v);
            id2=edge[i].id;
        }
        if(edge[i].w>ans) break;
    }
    for(int i=0;i<edge.size();i++)
    {
        if(edge[i].t!=kind)
        {
            unite(edge[i].u,edge[i].v);
            id1=edge[i].id;
            if(suma[id1]+sumb[id2]-cnt>=k)
            {
                cout << ans+edge[i].w;
                break;
            }
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~
Main.cpp:223:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~
Main.cpp:232:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |     for(int i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 8