The editorial of the problem very briefly explain which I can’t understand, Can anyone explain the solution to the problem.
thank you!
1 Like
It seems to be a problem of dsu and decomposition.
1 Like
on a2oj it was on mo’s algorithm category
A2oj is poorly maintained and outdated, I’d recommend stopstalk, It’s way better.
Consider each color separately.
All colors are divided into two types: the number of points involved >\sqrt {n} and the number of points involved \le\sqrt {n}.
For the first color, each query is processed sequentially after maintain the reduction points by dsu. If the two points are connected, the answer is added one.
For the second color, we can judge whether the two points are connected or not.
If connected, use another map to record the answer.
Finally, add up the answers of the two parts.
Details are due to the re-initialization of each color after processing dsu. For the first color, only memset is needed.
The total number of the second color may be more, so revoke the previous operation by dsu.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second
typedef pair <int, int> PII;
const int N = 1e5 + 10;
struct node{ int x, y, ans; } q[N];
unordered_map <int, int> mp[N];
map <PII, int> id, ret;
vector <int> v[N];
vector <node> e[N];
stack <PII> s;
int n, m, qu, cnt, line;
int father[N], c[N];
int getfather(int x){ return father[x] ? father[x] = getfather(father[x]) : x; }
int gf(int x){
if (father[x]){
s.push(MP(x, father[x]));
father[x] = getfather(father[x]);
return father[x];
}
else return x;
}
int main(){
scanf("%d%d", &n, &m);
rep(i, 1, m){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (x > y) swap(x, y);
mp[z][x] = mp[z][y] = 1;
e[z].push_back({x, y});
}
scanf("%d", &qu);
rep(i, 1, qu){
scanf("%d%d", &q[i].x, &q[i].y);
if (q[i].x > q[i].y) swap(q[i].x, q[i].y);
id[MP(q[i].x, q[i].y)] = i;
}
rep(i, 1, m){
int now = (int)mp[i].size();
if (now > 0) v[now].push_back(i);
}
line = sqrt(n);
rep(i, 1, line){
for (auto col : v[i]){
while (!s.empty()) s.pop();
for (auto edge : e[col]){
int x = edge.x, y = edge.y;
int fx = gf(x), fy = gf(y);
if (fx != fy){
s.push(MP(fx, father[fx]));
father[fx] = fy;
}
}
cnt = 0;
for (auto u : mp[col]) c[++cnt] = u.fi;
rep(j, 1, cnt - 1){
rep(k, j + 1, cnt){
int x = c[j], y = c[k];
if (x > y) swap(x, y);
if (gf(x) == gf(y)) ++ret[MP(x, y)];
}
}
while (!s.empty()){
father[s.top().fi] = s.top().se;
s.pop();
}
}
}
rep(i, line + 1, n){
for (auto col : v[i]){
memset(father, 0, sizeof father);
for (auto edge : e[col]){
int x = edge.x, y = edge.y;
int fx = getfather(x), fy = getfather(y);
if (fx != fy) father[fx] = fy;
}
rep(j, 1, qu) if (getfather(q[j].x) == getfather(q[j].y)) ++q[j].ans;
}
}
rep(i, 1, qu) printf("%d\n", q[i].ans + ret[MP(q[i].x, q[i].y)]);
return 0;
}
2 Likes
Thnks a lot 