제출 #1144171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144171		gramathegod	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	760 ms	100220 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

class DSU{
public:
    vector<int> parent, size;
    DSU(int n){
        parent.resize(n+1);
        size.resize(n+1,1);
        for (int i=1;i<=n;i++){
            parent[i]=i;
        }
    }
    int find(int x){
        if (parent[x]!=x){
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y){
        int rootX=find(x);
        int rootY=find(y);
        if (rootX!=rootY){
            if (size[rootX]>size[rootY]){
                parent[rootY]=rootX;
                size[rootX]+=size[rootY];
            }
            else{
                parent[rootX]=rootY;
                size[rootY]+=size[rootX];
            }
        }
    }
};

int main() {

    int n,m,u,v;
    char c;
    cin>>n>>m;
    DSU dsu(n);
    vector<pair<int, int>> bus;
    for (int i=0;i<m;i++){
        cin>>u>>v>>ws>>c;
        if (c=='T'){
            dsu.unite(u,v);
        }
        else{
            bus.push_back({u,v});
        }
    }
    unordered_map<int, int> train;
    for (int i=1;i<=n;i++){
        train[dsu.find(i)]++;
    }
    unordered_map<int, set<int>> graph;
    for (auto& b : bus){
        int u=b.first, v=b.second;
        int rootu=dsu.find(u);
        int rootv=dsu.find(v);
        if (rootu!=rootv){
            graph[rootu].insert(rootv);
            graph[rootv].insert(rootu);
        }
    }
    int rez=0;
    for (auto& t : train){
        size_t visited=graph[t.first].size();
        if (visited + 1  == train.size()){
            rez+=t.second;
        }
    }
    cout<<rez;
    return 0;
}

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