Submission #1241173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241173		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	65 / 100	3095 ms	20000 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);

    for (int i=1;i<=n;++i){parents[i]=i;sizep[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;

                }else{

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

                }


            }
        }else{


            connections[a].push_back(b);
            connections[b].push_back(a);
        }
    }
    int c=0;
    for (int nodo = 1; nodo<=n;++nodo){
        int sp = getparent(nodo);
        if (c==n)break;

        if (!covered2[sp]){
            covered2[sp]=true;


            memset(covered, 0, sizeof covered);

            int x=sizep[sp];

            for (int i = 1;i<=n;++i){
                int p=getparent(i);
                if (p!=sp && !covered[p]){

                    for (int it  :  connections[i]){

                        if (getparent(it)==sp){

                            x+=sizep[p];
                            covered[p]=1;
                            break;

                        }


                    }


                }


            }

            if (x==n)c+=sizep[sp];//absolute cinema

        }

    }

    cout<<c;


    return 0;
}

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