oj.uz

답안 #920901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920901 2024-02-03T07:31:16 Z theghostking1 Monthly railway pass (LMIO18_menesinis_bilietas) C++17
6 / 100
 693 ms 89956 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU{
	vector<int> parent,sz;
	DSU(int n){
		parent.resize(n);
		for (int i = 0; i<n; i++){
			parent[i] = i;
		}
		sz.resize(n,1);
	}
	int find(int x){
		if (x != parent[x]){
			return parent[x] = find(parent[x]);	
		}
		return x;
	}
	bool merge(int a, int b){
		a = find(a);
		b = find(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a,b);
		parent[b] = a;
		sz[a] += sz[b];
		return true;
	}
	int getsz(int x){
		x = find(x);
		return sz[x];
	}
};

vector<set<int>> adj;

int main(){
	int n,m;
	cin >> n >> m;
	adj.resize(n);
	DSU dsu = DSU(n);
	DSU ck = DSU(n);
	vector<array<int,2>> all;
	for (int i = 0; i<m; i++){
		int a,b;
		char c;
		cin >> a >> b >> c;
		a--;b--;
		if (c == 'T'){
			dsu.merge(a,b);
		}
		ck.merge(a,b);
		if (c == 'T') continue;
		all.push_back({a,b});
	}
	if (ck.getsz(0) != n){
		cout << 0 << '\n';
	}
	else{
		set<int> tot;
		for (int i = 0; i<n; i++){
			tot.insert(dsu.find(i));
		}
		int num = tot.size();
		for (int i = 0; i<(int)all.size(); i++){
			int one = all[i][0];
			int two = all[i][1];
			one = dsu.find(one);
			two = dsu.find(two);
			if (one == two) continue;
			adj[one].insert(two);
			adj[two].insert(one);
		}
		int cnt = 0;
		for (int i = 0; i<n; i++){
			if (adj[i].size() == num-1){
				cnt += dsu.getsz(i);
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |    if (adj[i].size() == num-1){
      |        ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 251 ms 22500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 29796 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1356 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 481 ms 41692 KB Output is correct
7 Correct 693 ms 89956 KB Output is correct
8 Correct 12 ms 3676 KB Output is correct
9 Correct 22 ms 5336 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 6 ms 856 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 6 ms 856 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 6 ms 856 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -