- P118's solution
P118's Solution
- 2025-9-14 20:21:40 @
这是经典并查集题目:
把每个电荷拆成两个结点 。
A x y
时连边 和 。A x y
时连边 和 。Q x y
时:- 与 连通就输出
A
。 - 与 连通就输出
R
。 - 都不连通就输出
?
。
- 与 连通就输出
#include <bits/stdc++.h>
using namespace std;
int ld[1000012], co[1000012], sz[1000012];
void init(int n)
{
for (int i = 1; i <= n; i++)
ld[i] = i, co[i] = 0, sz[i] = 1;
}
pair<int, int> want(int x)
{
stack<pair<int, int> > s;
s.push(make_pair(x, 0));
int tc = 0, y = x;
while (ld[x] != x)
{
tc += co[x];
x = ld[x];
s.push(make_pair(x, tc));
}
while (!s.empty())
{
pair<int, int> u = s.top();
s.pop();
ld[u.first] = x;
co[u.first] = tc - u.second;
}
return make_pair(ld[y], co[y]);
}
void add(int x, int y, int c)
{
x = want(x).first, y = want(y).first;
if (x == y) return;
ld[y] = x, co[y] = c, sz[x] += sz[y], sz[y] = 0;
}
bool tg(int x, int y)
{
pair<int, int> xx = want(x), yy = want(y);
return (xx.first == yy.first);
}
int dis(int x, int y)
{
pair<int, int> xx = want(x), yy = want(y);
return xx.second - yy.second;
}
int main()
{
int n, m;
cin >> n >> m;
init(2 * n);
while (m--)
{
char c;
int x, y;
cin >> c >> x >> y;
if (c == 'A') add(x, y + n, 0), add(x + n, y, 0);
if (c == 'R') add(x, y, 0), add(x + n, y + n, 0);
if (c == 'Q')
{
if (tg(x, y + n)) puts("A");
else if (tg(x, y)) puts("R");
else puts("?");
}
}
return 0;
}