Submission #392447

#	Time	Username	Problem	Language	Result	Execution time	Memory
392447		keta_tsimakuridze	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	542 ms	64936 KiB

menesinis_bilietas

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=5e5+5,mod=1e9+7;
int par[N],u,v,n,m,fix[N],comp;
char t;
vector<int>c[N],V[N];
string s;
void merge(int u,int v){
	u=par[u];
	v=par[v];
	if(u==v) return;
	comp--;
	if(c[u].size()<c[v].size()) swap(u,v);
	for(int i=0;i<c[v].size();i++){
		c[u].push_back(c[v][i]);
		par[c[v][i]] = u;
	}
}
 main(){
	// t=1;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		par[i] = i;
		c[i].push_back(i);
	} comp = n;
	int ans = 0;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>t;
		if(t=='T') merge(u,v);
		else V[u].push_back(v),V[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(par[i]!=i) continue;
		int cnt = 0; 
		for(int j=0;j<c[i].size();j++){
			v=c[i][j];  
			for(int k=0;k<V[v].size();k++){
				if(fix[par[V[v][k] ] ]!= i && par[V[v][k]]!=i) {
					fix[par[V[v][k]]]=i;
					cnt++;
				}
			}
		}
		if(cnt == comp-1) ans+=c[i].size();
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'void merge(long long int, long long int)':
menesinis_bilietas.cpp:17:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<c[v].size();i++){
      |              ~^~~~~~~~~~~~
menesinis_bilietas.cpp: At global scope:
menesinis_bilietas.cpp:22:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 |  main(){
      |       ^
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:38:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int j=0;j<c[i].size();j++){
      |               ~^~~~~~~~~~~~
menesinis_bilietas.cpp:40:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int k=0;k<V[v].size();k++){
      |                ~^~~~~~~~~~~~

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