Submission #382249

#	Time	Username	Problem	Language	Result	Execution time	Memory
382249		fadi57	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	950 ms	92636 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mx=500006;
const int mod= 1e9+7 ;
const ll inf=0;



//***while there is life there is hope
int n,m;

int siz[mx];int par[mx];vector<pair<int,int>>adj[mx];
void init(){

for(int i=1;i<=n;i++){
    par[i]=i;
    siz[i]=1;
}

 }
int root(int node){
if(par[node]==node){
return node;

}else{
   return par[node]=root(par[node]);

 }
}
void uni(int x,int y){

    int a=root(x);
    int b=root(y);
if(siz[a]<siz[b]){swap(a,b);}

par[b]=a;
siz[a]+=siz[b];

 }
 int isa(char x){

 return (x=='A');
 }
 int a[mx];

int main() {
cin>>n>>m;
int sec=0;
init();
for(int i=0;i<m;i++){
int x,y;char t;
cin>>x>>y>>t;



    adj[x].push_back({y,isa(t)});
    adj[y].push_back({x,isa(t)});
  if(isa(t)==0){
    uni(x,y);
  }
}
set<int>comp;
vector<int>v[n+1];
for(int i=1;i<=n;i++){
   //cout<<par[i]<<" "<<siz[i]<<endl;
   comp.insert(root(i));
   v[root(i)].push_back(i);
}
int ans=0;

for(int i = 1 ; i <= n ; ++i)
	{

	    if(!v[i].size()){continue;}
	    set<int>s;s.insert(i);
	    for(auto it:v[i]){
            for(auto itt:adj[it]){
                s.insert(root(itt.first));
            }
	    }ans+=(comp.size()==s.size())*v[i].size();
	}cout<<ans;



}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:50:5: warning: unused variable 'sec' [-Wunused-variable]
   50 | int sec=0;
      |     ^~~

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