제출 #1241166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241166		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	181 ms	16264 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];
int sizep[N];

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

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

    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 sp = getparent(1);

        int c=sizep[sp]-1;

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

                for (int it  :  connections[i]){

                    if (getparent(it)==sp){

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

                    }


                }


            }


        }





    cout<<c;


    return 0;
}

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