oj.uz

Submission #258733

# Submission time Handle Problem Language Result Execution time Memory
258733 2020-08-06T12:59:09 Z uacoder123 Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 996 ms 77904 KB 
#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,c=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;
            r[pf]++;
        }
        else
        {
            par[pf]=ps;
            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);
        al[pf].insert(ps);
        al[ps].insert(pf);
    }
    for(int i=1;i<=n;++i)
        if(al[find(i)].size()==t-1)
            c++;
    cout<<c<<endl;
    return(0);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 33272 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 17 ms 27520 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 184 ms 26232 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27520 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 14 ms 23936 KB Output is correct
4 Correct 21 ms 24704 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 803 ms 64820 KB Output is correct
7 Correct 996 ms 77904 KB Output is correct
8 Correct 33 ms 25724 KB Output is correct
9 Correct 50 ms 27376 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Incorrect 22 ms 24320 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Incorrect 22 ms 24320 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Incorrect 22 ms 24320 KB Output isn't correct
6 Halted 0 ms 0 KB -