Submission #1241161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241161		pcp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	234 ms	38720 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]==-1 || parents[node]==node)return parents[node]=node;
    else return parents[node] = getparent(parents[node]);
}

vector<int> connections[N];
vector<int> t_connections[N];

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

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

    memset(parents, -1, sizeof parents);




    for (int i = 0 ; i < m ; ++i){
        char w;
        int aa,bb;cin>>aa>>bb>>w;
        int a,b;
        a = (aa>=bb) ? aa : bb;
        b = (a==aa) ? bb : aa;


        if (w=='T'){
        parents[a]=b;
        t_connections[a].push_back(b);
        t_connections[b].push_back(a);
        }else{ connections[a].push_back(b);connections[b].push_back(a); }

    }

    int c=0;

    memset(covered, 0, sizeof covered);

    memset(sizep, 0, sizeof sizep);

    for (int i = 2; i <= n;++i)++sizep[getparent(i)];


    c+=sizep[1];
    covered[1]=true;


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

            for (int j = 0; j < connections[i].size();++j){

                if (getparent(connections[i][j]) == 1 ){

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

                }


            }


        }



    }

    cout<<c<<endl;


    return 0;
}

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