Submission #920869

#	Time	Username	Problem	Language	Result	Execution time	Memory
920869		Sandarach151	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	580 ms	90656 KiB

menesinis_bilietas

#include<bits/stdc++.h>
using namespace std;

vector<int> link;
vector<int> sizes;

int find(int x){
    while(x!=link[x]) x = link[x];
    return x;
}

bool same(int a, int b){
    return find(a)==find(b);
}

void unite(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        if(sizes[a]<sizes[b]) swap(a, b);
        link[b] = a;
        sizes[a] += sizes[b];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<pair<int, bool> > adg[n];
    vector<pair<int, int> > bus;
    link.resize(n);
    sizes.resize(n);
    int newsize[n];
    for(int i=0; i<n; i++){
        link[i]=i;
        sizes[i]=1;
        newsize[i]=0;
    }
    for(int i=0; i<m; i++){
        int a, b;
        char t;
        cin >> a >> b >> t;
        a--;
        b--;
        adg[a].push_back(make_pair(b, (t=='T')));
        adg[b].push_back(make_pair(a, (t=='T')));
        if(t=='T') unite(a, b);
        else bus.push_back(make_pair(a, b));
    }
    set<int> newgraph[n];
    for(auto u : bus){
        if(find(u.first)!=find(u.second)){
            if(newgraph[find(u.first)].count(find(u.second))==0){
                newsize[find(u.first)]+=sizes[find(u.second)];
                newsize[find(u.second)]+=sizes[find(u.first)];
                newgraph[find(u.first)].insert(find(u.second));
                newgraph[find(u.second)].insert(find(u.first));
            }
        }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        if(newsize[i]+sizes[i]==n){
            ans+=sizes[i];
        }
    }
    cout << ans << '\n';
    return 0;
}

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