Submission #1239127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239127		asdfghqwert	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	222 ms	61256 KiB

menesinis_bilietas

//#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC optimize("O3,Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
typedef int ll;
using namespace std;
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m , ans = 0;cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<vector<int>> g2(n + 1);
    for(int i = 1 ; i <= m ; i++){
        char ty;
        int u , v;cin >> u >> v >> ty;
        if(ty == 'T'){g[u].push_back(v); g[v].push_back(u);}
        if(ty == 'A'){g2[u].push_back(v); g2[v].push_back(u);}
    }
    vector<bool> seen (n + 1);vector<int> vc(n + 1);
    vector<vector<int>> components;
    for(int i = 1 ; i <= n ; i++){
        if(seen[i])continue;
        vector<int> vertex , que = {i};
        seen[i] = 1;
        while(!que.empty()){
            int u = que.back();
            vertex.push_back(u);
            que.pop_back();
            for(int v : g[u]){
                if(seen[v])continue;
                que.push_back(v);
                seen[v] = 1;
            }
        }
        int idx = components.size();
        components.push_back(vertex);
    }
    vector<bool> mark(components.size());
    for(int p = 0 ; p < components.size() ; p++)for(int &u : components[p])vc[u] = p;
    for(int p = 0 ; p < components.size() ; p++){
        vector<int> opr = {p};
        int cnt = 1 ;
        mark[p] = 1;
        for(int &u : components[p]){
            for(int v : g2[u]){
                if(!mark[vc[v]]){
                    opr.push_back(vc[v]);
                    mark[vc[v]] = 1;
                    cnt++;
                }
            }
        }
        if(cnt == components.size())ans+= components[p].size();
        for(int &u : opr)mark[u] = 0;
    }
    cout << ans;
}

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