Submission #1306345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306345		Sofiatpc	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	562 ms	69832 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 5*1e5+5;
int p[MAXN], s[MAXN], marc[MAXN];
set<int> adj[MAXN];

int find(int x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}

void merge(int a, int b){
    a = find(a), b = find(b);

    if(a == b)return;

    if(s[a] < s[b])swap(a,b);

    s[a] += s[b];
    p[b] = a; 
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m; cin>>n>>m;

    for(int i = 1; i <= n; i++){
        p[i] = i; s[i] = 1;
    }

    vector<int> va,vb;
    for(int i = 1; i <= m; i++){
        int a,b; char c; cin>>a>>b>>c;
        if(c == 'T') merge(a,b);
        else { va.push_back(a); vb.push_back(b); }
    }

    for(int i = 0; i < sz(va); i++)
        if( find(va[i]) != find(vb[i]) ){
            adj[ find(va[i]) ].insert( find(vb[i]) );
            adj[ find(vb[i]) ].insert( find(va[i]) );
        }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(marc[ find(i) ] == 0){
            int qtd = s[find(i)];
            for(int viz : adj[ find(i) ])qtd += s[viz];
            if(qtd == n)marc[ find(i) ] = 1;
            else marc[ find(i) ] = 2;
        }

        if(marc[find(i)] == 1)ans++;
    }
    cout<<ans<<"\n";
}

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