이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
//UnionFind
struct UnionFind{
private:
int N;
vector<int> par,sz;
public:
void init(int n){
N = n;
par.clear();
sz.clear();
for(int i=0; i<N; i++){
par.push_back(i);
sz.push_back(1);
}
}
int root(int a){
if(par[a] == a) return a;
return par[a] = root(par[a]);
}
bool isSame(int a, int b){
return (root(a) == root(b));
}
void unite(int a, int b){
if(isSame(a, b)) return;
if(sz[root(a)] < sz[root(b)]){
sz[root(b)] += sz[root(a)];
sz[root(a)] = 0;
par[root(a)] = root(b);
}
else{
swap(a, b);
sz[root(b)] += sz[root(a)];
sz[root(a)] = 0;
par[root(a)] = root(b);
}
}
int size(int a){
return sz[root(a)];
}
void print(){
for(int i=0; i<N; i++) cout << sz[i] << " ";
cout << endl;
}
};
int N,M,Q;
UnionFind uf;
vector<pair<pair<int,int>, pair<int,int>>> all; //cost, type, a, b
vector<pair<int,int>> ans;
int main(){
cin >> N >> M;
uf.init(N);
for(int i=0; i<M; i++){
int a, b, c;
cin >> a >> b >> c;
all.push_back(MP(MP(c, 1),MP(a-1,b-1)));
}
cin >> Q;
for(int i=0; i<Q; i++){
int t, a, b;
cin >> t >> a >> b;
all.push_back(MP(MP(b, -i),MP(a-1,0)));
}
sort(all.begin(), all.end());
reverse(all.begin(), all.end());
for(int i=0; i<all.size(); i++){
if(all[i].first.second == 1){
uf.unite(all[i].second.first, all[i].second.second);
//cout << "unite: " << all[i].second.first << " " << all[i].second.second << endl;
}
else{
ans.push_back(MP(-all[i].first.second, uf.size(all[i].second.first)));
//cout << "ans: " << all[i].second.first << " " << uf.size(all[i].second.first) << endl;
//uf.print();
}
}
sort(ans.begin(), ans.end());
for(int i=0; i<ans.size(); i++) cout << ans[i].second << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'int main()':
bridges.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<all.size(); i++){
~^~~~~~~~~~~
bridges.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ans.size(); i++) cout << ans[i].second << endl;
~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |