Submission #1241174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241174		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	65 / 100	3094 ms	38980 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);
        }
    }
    int c=0;
    for (auto nodeichon : amongos){
        int sp = nodeichon;


            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