Submission #639608

#	Time	Username	Problem	Language	Result	Execution time	Memory
639608		teesla	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	30 / 100	3093 ms	29920 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>ii;
const int maxn=1e5+10;
vector<ii>adj[5*maxn];
int visitado[5*maxn];

int n,m;

void bfs(int x){
	visitado[x]=0;
	priority_queue<ii,vector<ii>,greater<ii>> fila;
	fila.push({0,x});

	while(!fila.empty()){
		int atual=fila.top().second,dist=fila.top().first;
		fila.pop();
		if(visitado[atual]!=-1 and dist>visitado[atual]) continue;
		visitado[atual]=dist;
		if(visitado[atual]>1)continue;

		for(int i=0; i<adj[atual].size(); i++){
			int viz=adj[atual][i].first, d=adj[atual][i].second;
			if(dist+d>1)continue;
			else if(visitado[viz]==-1 and dist+d<=1){
				visitado[viz]=d+dist;
				fila.push({d+dist,viz});
			}
			else if(visitado[viz]>dist+d){
				visitado[viz]=dist+d;
				fila.push({d+dist,viz});
			}
		}
	}
	return;
}

int main(){
	cin >> n>> m;
	for(int i=0; i<m; i++){
		int a,b;
		char c;
		cin >> a >> b >> c;
		if(c=='T'){
			adj[a].push_back({b,0});
			adj[b].push_back({a,0});
		}
		else{
			adj[a].push_back({b,1});
			adj[b].push_back({a,1});
		}
	}
	int res=0;

	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++) visitado[j]=-1;
		bfs(i);
		int ok=1;
		for(int j=1; j<=n; j++){
			if(visitado[j]==-1 or visitado[j]>1){
				ok=0;
				break;
			}
		}
		//if(ok)cout << i<<endl;
		//cout << ok<<endl;
		res+=ok;
	}
	cout << res<<endl;
	return 0;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'void bfs(int)':
menesinis_bilietas.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0; i<adj[atual].size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~

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