제출 #409401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409401		MOUF_MAHMALAT	다리 (APIO19_bridges)	C++14	14 / 100	497 ms	19652 KiB

bridges

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
struct node
{
    ll u1,u2,w;
} a[100009];
ll n,edg,q,p[200009],mn[200009],dp[200009][20],ans[200009];
vector<vector<ll> >v;
bool cmp(const node&x,const node&y)
{
    return x.w>y.w;
}
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y,ll z)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return;
    n++;
    mn[n]=z;
    ans[n]=ans[x]+ans[y];
    dp[n][0]=dp[x][0]=dp[y][0]=n;
    p[n]=p[x]=p[y]=n;
    v[n].push_back(x);
    v[n].push_back(y);
}
ll op(ll x,ll k)
{
    for(ll i=0; i<20; i++)
        if(k&(1<<i))
            x=dp[x][i];
    return x;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll x,y,z;
    cin>>n>>edg;
    v.resize(n+edg+9);
    for(ll i=0; i<edg; i++)
    {
        cin>>x>>y>>z;
        a[i]= {x,y,z};
    }
    sort(a,a+edg,cmp);
    for(ll i=1; i<=n; i++)
        p[i]=dp[i][0]=i,ans[i]=1;

    for(ll i=0; i<edg; i++)
        mrg(a[i].u1,a[i].u2,a[i].w);

    for(ll j=1; j<20; j++)
        for(ll i=1; i<=n; i++)
            dp[i][j]=dp[ dp[i][j-1] ][j-1];
    cin>>q;
    while(q--)
    {
        cin>>x>>x>>y;
        ll l=0,r=2e5,m;
        while(r-l>1)
        {
            m=(l+r)/2;
            if(mn[op(x,m)]>=y)
                l=m;
            else
                r=m;
        }
        cout<<ans[op(x,l)]<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27