Submission #1241195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241195		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	3096 ms	39380 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#include <iostream>
#define ll long long



using namespace std;
const int N=500010;

int parents[N];

int getparent(int node){
    if ( parents[node]==node)return parents[node]=node;
    else return parents[node] = getparent(parents[node]);
}

vector<int> connections[N];

bool covered[N];
bool covered2[N];
int sizep[N];

int main(){
    int n,m;cin>>n>>m;

    memset(sizep,0,sizeof sizep);
    memset(covered,0, sizeof covered);
    memset(covered2,0, sizeof covered2);

    set<int> amongos;

    for (int i=1;i<=n;++i){parents[i]=i;sizep[i]++;amongos.insert(i);}

    for (int i = 0;i<m;++i){

        char w;int a,b;cin>>a>>b>>w;
        int pa=getparent(a);
        int pb=getparent(b);
        if (w=='T'){
            if (pa!=pb){

                if (sizep[pa]>sizep[pb]){

                    sizep[pa]+=sizep[pb];
                    parents[pb]=pa;

                    amongos.erase(pb);

                }else{

                    sizep[pb]+=sizep[pa];
                    parents[pa]=pb;

                    amongos.erase(pa);

                }


            }
        }else{


            connections[a].push_back(b);
            connections[b].push_back(a);
        }
    }



    for (int i = 1; i < n; ++i){


            if (i!=getparent(i)){

                bool done[N];
                memset(done, false, sizeof done);
                for (int it : connections[i]){

                        if (!done[getparent(it)]){done[getparent(it)]=true;
                        connections[getparent(i)].push_back(getparent(it));
                        }
                }


            }


    }
    int c=0;
    for (auto nodeichon : amongos){

            int k = sizep[nodeichon];

            memset(covered, 0, sizeof covered);

            for (int con : connections[nodeichon]){

                if (!covered[getparent(con)]){
                    covered[getparent(con)]=true;k+=sizep[getparent(con)];

                }


            }

            if (k==n)c+=sizep[nodeichon];

    }

    cout<<c;


    return 0;
}

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