Submission #806299

#	Time	Username	Problem	Language	Result	Execution time	Memory
806299		NekoRolly	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	174 ms	37460 KiB

menesinis_bilietas

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+4;

struct Dsu
{
    int rt[N],h[N],sz[N];

    void build(int n){
        for (int i=1; i<=n; i++){
            h[i] = 1, sz[i] = 1;
            rt[i] = i;
        }
    }

    int find(int a){
        if (a == rt[a]) return a;
        return rt[a] = find(rt[a]);
    }

    void join(int a,int b){
        a = find(a), b = find(b);
        if (a == b) return;
        if (h[a] > h[b]){
            swap(a, b);
        }
        h[b] += (h[a] == h[b]);
        sz[b] += sz[a];
        rt[a] = b;
    }
};

int n,m;
int cnt,ans;
Dsu d;
int Ed_n;
int Ed_a[N],Ed_b[N];
vector<int> adj[N];

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

    cin >> n >> m;

    d.build(n);

    for (int i=0; i<m; i++){
        int a,b;
        char c;
        cin >> a >> b >> c;
        if (c == 'T'){
            d.join(a, b);
        }
        if (c == 'A'){
            Ed_a[Ed_n] = a;
            Ed_b[Ed_n] = b;
            Ed_n++;
        }
    }

    for (int i=0; i<Ed_n; i++){
        int a = d.find(Ed_a[i]);
        int b = d.find(Ed_b[i]);
        if (a == b) continue;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i=1; i<=n; i++){
        if (i != d.find(i)) continue;
        vector<int> & v = adj[i];
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        cnt++;
    }

    // cout << "cnt : " << cnt << "\n";

    for (int i=1; i<=n; i++){
        if (i != d.find(i)) continue;
        if (adj[i].size() + 1 == cnt){
            ans += d.sz[i];
        }
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:83:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         if (adj[i].size() + 1 == cnt){
      |             ~~~~~~~~~~~~~~~~~~^~~~~~

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