제출 #1241197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241197		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	468 ms	88592 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<pair<int,int>> connections2;
set<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{


            connections2.push_back({a,b});
        }
    }

    for (pair<int,int> it : connections2){

        int pa = getparent(it.first);
        int pb = getparent(it.second);


        if (pa!=pb){

            connections[pa].insert(pb);
            connections[pb].insert(pa);

        }


    }


    int c=0;
    for (auto nodeichon : amongos)if (connections[nodeichon].size() == amongos.size()-1)c+=sizep[nodeichon];



    cout<<c;


    return 0;
}

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