oj.uz

답안 #198450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198450 2020-01-26T05:42:29 Z oolimry Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 558 ms 75180 KB 
#include <bits/stdc++.h>

using namespace std;
static int p[500005];
int numSets;
int findSet(int u){
	if(p[u] == u) return u;
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}

void unionSet(int u, int v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return;
	p[u] = v;
	numSets--;
}

typedef pair<int,int> ii; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> n >> m;
	numSets = n;
	unordered_set<int> edges[n];
	for(int i = 0;i < n;i++) p[i] = i;
	vector<ii> bus;
	for(int i = 0;i < m;i++){
		int u, v; char c;
		cin >> u >> v >> c;
		u--; v--;
		if(c == 'T'){
			unionSet(u,v);
		}
		else{
			bus.push_back(ii(u,v));
		}
	}
	
	for(ii e : bus){
		int u = findSet(e.first);
		int v = findSet(e.second);
		edges[u].insert(v);
		edges[v].insert(u);
	}
	
	int ans = 0;
	for(int i = 0;i < n;i++){
		if(numSets - 1 == edges[findSet(i)].size()) ans++;
	}
	
	cout << ans << "\n";
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(numSets - 1 == edges[findSet(i)].size()) ans++;
      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 24696 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 27 ms 27896 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 47 ms 3192 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 27896 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 9 ms 1144 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 558 ms 40288 KB Output is correct
7 Correct 549 ms 75180 KB Output is correct
8 Correct 14 ms 3064 KB Output is correct
9 Correct 23 ms 4472 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Incorrect 9 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Incorrect 9 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Incorrect 9 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -