| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 422259 | dreezy | Friend (IOI14_friend) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
/*******************/
#define pi pair<int,int>
#define ll long long
#define f first
#define s second
#define pb push_back
struct UnionFind{
vector<int> parent, height, sz;
void init(int n){
height.clear();
height.assign(n, 0);
parent.clear();
parent.assign(n, 0);
sz.clear();
sz.assign(n, 1);
for(int i=0; i<n ;i++){
parent[i] = i;
}
}
int root(int n){
if(parent[n]!= n)
parent[n] = root(parent[n]);
return parent[n];
}
bool same(int n1, int n2){
return root(n1) == root(n2);
}
void join(int n1, int n2){
int r1 = root(n1);
int r2 = root(n2);
if(height[r1] > height[r2]){
parent[r2] = r1;
height[r1] = max(height[r1], height[r2] + 1);
sz[r1] += sz[r2];
//cout << sz[r1]<<"; "<<sz[r2]<<endl;
}else{
parent[r1] = r2;
height[r2] = max(height[r2], height[r1] + 1);
sz[r2]+=sz[r1];
//cout << sz[r1]<<";; "<<sz[r2]<<endl;
}
}
};
int findSample(int n,int confidence[],int host[],int protocol[]){
UnionFind uf;
uf.init(n);
for(int i =1; i<n; i++){
if(protocol[i] == 1){
uf.join(i, host[i]);
//cout << i <<", "<<host[i]<<endl;
}
}
set<int> roots;
for(int i =0;i < n; i++){
roots.insert(uf.root(i));
}
int ans =0;
for(int rt : roots){
//cout <<rt<<": "<< uf.sz[rt]<<endl;
ans = max(ans, uf.sz[rt]);
}
return max(ans, roots.size());
}
/*******************/