oj.uz

Submission #258736

# Submission time Handle Problem Language Result Execution time Memory
258736 2020-08-06T13:02:08 Z uacoder123 Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 972 ms 71612 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,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);
        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

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:72: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 26184 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 17 ms 27444 KB Output is correct
5 Correct 14 ms 23936 KB Output is correct
6 Correct 180 ms 23924 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27444 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 14 ms 23936 KB Output is correct
4 Correct 22 ms 24576 KB Output is correct
5 Correct 14 ms 23936 KB Output is correct
6 Correct 799 ms 60408 KB Output is correct
7 Correct 972 ms 71612 KB Output is correct
8 Correct 33 ms 25588 KB Output is correct
9 Correct 50 ms 26992 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 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 18 ms 24064 KB Output is correct
5 Correct 23 ms 24320 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Correct 24 ms 24320 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 13 ms 23808 KB Output is correct
13 Correct 16 ms 23936 KB Output is correct
14 Incorrect 15 ms 23936 KB Output isn't correct
15 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 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 18 ms 24064 KB Output is correct
5 Correct 23 ms 24320 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Correct 24 ms 24320 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 13 ms 23808 KB Output is correct
13 Correct 16 ms 23936 KB Output is correct
14 Incorrect 15 ms 23936 KB Output isn't correct
15 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 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 18 ms 24064 KB Output is correct
5 Correct 23 ms 24320 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Correct 24 ms 24320 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 13 ms 23808 KB Output is correct
13 Correct 16 ms 23936 KB Output is correct
14 Incorrect 15 ms 23936 KB Output isn't correct
15 Halted 0 ms 0 KB -