Submission #258739

#	Time	Username	Problem	Language	Result	Execution time	Memory
258739		uacoder123	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	974 ms	72484 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
set<int> al[500001];
int n,m,t,co=0;
int par[500001],r[500001]={};
vector<ii> ed;
int find(int f)
{
    if(par[par[f]]!=par[f]) par[f]=find(par[f]);
    return(par[f]);
}
void mer(int f,int s)
{
    int pf=find(f),ps=find(s);
    if(pf!=ps)
    {
        if(r[pf]>=r[ps])
        {
            par[ps]=pf;
            if(r[ps]==r[pf])
            r[pf]++;
        }
        else
        {
            par[pf]=ps;
            if(r[ps]==r[pf])
            r[ps]++;
        }
        t--;
    }
}
int main()
{
    cin>>n>>m;
    t=n;
    for(int i=1;i<=n;++i)
    {
        par[i]=i;
        r[i]=1;
    }
    for(int i=0;i<m;++i)
    {
        char c;
        int f,s;
        cin>>f>>s>>c;
        if(c=='A')
            ed.pb(mp(f,s));
        else
            mer(f,s);
    }
    for(int i=0;i<ed.size();++i)
    {
        int pf=find(ed[i].F),ps=find(ed[i].S);
        if(ps!=pf)
        {
            al[pf].insert(ps);
            al[ps].insert(pf);
        }
    }
    for(int i=1;i<=n;++i)
        if(al[find(i)].size()>=t-1)
            co++;
    cout<<co<<endl;
    return(0);
} 

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ed.size();++i)
                 ~^~~~~~~~~~
menesinis_bilietas.cpp:75:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(al[find(i)].size()>=t-1)
            ~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 19 / 19