| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1358032 | po_rag526 | A Plus B (IOI23_aplusb) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int p[300005],len[300005],dist[300005];
vector<int> adj[300005];
bitset<300005> vis;
queue<int> q;
vector<int> want;
int find(int u) {
if(p[u] == u) return u;
return p[u] = find(p[u]);
}
int main() {
ios_base::sync_with_stdio(0),cin.tie(0);
int n,m,qq;cin>>n>>m>>qq;
for(int i = 1 ; i<=n ; ++i) p[i] = i;
for(int i = 1 ; i<=m ;++i) {
int a,b;cin>>a>>b;
adj[a].push_back(b),adj[b].push_back(a);
p[find(a)] = find(b);
}
for(int i = 1 ; i<=n ; ++i) {
if(vis[i]) continue;
while(q.size()) q.pop();
q.push(i),vis[i] = 1;
int last;
while(q.size()) {
int x = q.front();q.pop();
last = x;
for(int y:adj[x]) {
if(!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
want.push_back(last);
}
vis.reset();
for(int x:want) {
while(q.size()) q.pop();
q.push(x);
dist[x] = 0,vis[x] = 1;
int mem = 0;
while(q.size()) {
int now = q.front();q.pop();
mem = dist[now];
for(int y:adj[now]) {
if(!vis[y]) {
vis[y] = 1;
dist[y] = dist[now]+1;
q.push(y);
}
}
}
len[find(x)] = mem;
}
while(qq--) {
int o;cin>>o;
if(o == 1) {
int a;cin>>a;
cout << len[find(a)] << "\n";
}
else {
int a,b;cin>>a>>b;
a = find(a),b = find(b);
p[a] = b;
len[b] = max({len[a],len[b],(len[a]+1)/2+(len[b]+1)/2+1});
}
}
}