Submission #529784

#	Time	Username	Problem	Language	Result	Execution time	Memory
529784		ammar2000	Bridges (APIO19_bridges)	C++17	0 / 100	127 ms	14272 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=3e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,m,q,si[SI],p[SI],ans[SI];
map <pair < ll,ll> ,ll> mp ;
vector <pair <ll,pair <ll,ll> > > v;
vector < pair < pair<ll,ll> ,ll> > qu;
ll root(int x)
{
    if (p[x]==x) return x;
    return p[x]=root(p[x]);
}
void connect(int x,int y)
{
    x=root(x);
    y=root(y);
    if (x==y)
       return;
    if (si[x]<si[y]) swap(x,y);
    si[x]+=si[y];
    p[y]=x;
}
int main()
{
   fast
   cin>>n>>m;
   for (int i=1;i<=n;i++)
    p[i]=i,si[i]=1;
   for (int i=0;i<m;i++)
   {
       ll x,y,w;
       cin>>x>>y>>w;
       if (x>y) swap (x,y);
       mp[{x,y}]=max(mp[{x,y}],w);
   }
   for (auto o:mp)
   {
       ll x=o.F.F,y=o.F.S,w=o.S;
       v.pb({w,{x,y}});
   }
   sort (all(v));
   reverse (all(v));
   cin>>q;
   for (int i=0;i<q;i++)
   {
       ll t,s,w;
       cin>>t>>s>>w;
       qu.pb({{w,s},i});
   }
   sort (all(qu));
   reverse(all(qu));
   ll vp=0,qp=0;
   while (qp<qu.size())
   {
       ll we=qu[qp].F.F;
       while (vp<v.size()&&v[vp].F>=we)
       {
           connect(v[vp].S.F,v[vp].S.S);
           vp++;
       }
       ans[qu[qp].S]=si[root(qu[qp].F.S)];
       qp++;
   }
   for (int i=0;i<n;i++)
    cout << ans[i]<<"\n";
   // use scanf not cin
   return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:67:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    while (qp<qu.size())
      |           ~~^~~~~~~~~~
bridges.cpp:70:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |        while (vp<v.size()&&v[vp].F>=we)
      |               ~~^~~~~~~~~

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