Submission #910863

#	Time	Username	Problem	Language	Result	Execution time	Memory
910863		ibm2006	Bridges (APIO19_bridges)	C++17	14 / 100	82 ms	18860 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,m,q,e,ee,a[1100000],h[1100000],dep[1100000],ans[1100000];
vector<pair<pair<ll,ll>,pair<ll,ll>>> u;
pair<pair<ll,ll>,pair<ll,ll>> pq;
ll f(ll x)
{
    if(a[x]==x)
        return x;
    a[x]=f(a[x]);
    return a[x];
}
void g(ll x,ll y)
{
    x=f(x);
    y=f(y);
    if(x==y)
        return;
    if(dep[x]>dep[y])
        swap(x,y);
    dep[y]+=dep[x];
    a[x]=y;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
    {
        a[i]=i;
        dep[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        u.push_back({{-z,1},{x,y}});
    }
    scanf("%lld",&q);
    for(i=1;i<=q;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        u.push_back({{-z,2},{i,y}});
    }
    sort(u.begin(),u.end());
    for(e=0;e<u.size();e++)
    {
        pq=u[e];
        if(pq.first.second==1)
        {
            x=pq.second.first;
            y=pq.second.second;
            g(x,y);
            continue;
        }
        x=pq.second.first;
        y=pq.second.second;
        ans[x]=dep[f(y)];
    }
    for(i=1;i<=q;i++)
    {
        printf("%lld\n",ans[i]);
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:45:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(e=0;e<u.size();e++)
      |             ~^~~~~~~~~
bridges.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
bridges.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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