综合性很强的题目。
存在环，可以用tarjan处理，然后需要求LCA。并查集+RMQ可以搞。
非常不错的题目。
/* 4297 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int v, nxt;
} edge_t; const int maxn = ;
// input
int link[maxn], link2[maxn]; // tarjan
int low[maxn], pre[maxn], bn[maxn], C[maxn];
int S[maxn], top;
int dfs_clock, block; // LCA
int head[maxn], l;
edge_t E[maxn<<];
int deg[maxn], beg[maxn];
int deep[maxn], V[maxn<<], D[maxn<<]; // RMQ
int dp[maxn<<][]; int dis[maxn];
int fa[maxn];
int n; int find(int x) {
if (x == fa[x])
return x; int tmp = fa[x];
fa[x] = find(fa[x]);
dis[x] += dis[tmp];
return fa[x];
} void tarjan(int u) {
S[top++] = u;
pre[u] = low[u] = ++dfs_clock; int v = link[u]; if (!pre[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (!bn[v]) {
low[u] = min(low[u], pre[v]);
} if (pre[u] == low[u]) {
++block;
C[block] = ;
do {
bn[S[--top]] = block;
++C[block];
} while (S[top] != u);
}
} void addEdge(int u, int v) {
E[l].v = v;
E[l].nxt = head[u];
head[u] = l++;
} void dfs(int u, int d) {
deep[u] = d;
V[++top] = u;
D[top] = d;
beg[u] = top; int v, k; for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (link2[v] == -) {
link2[v] = link2[u];
}
dfs(v, d+);
V[++top] = u;
D[top] = d;
}
} void RMQ_init() {
int len = top;
int i, j, k; for (i=; i<=len; ++i)
dp[i][] = i;
for (j=; (<<j)<=len; ++j) {
for (i=; i+(<<j)-<=len; ++i) {
if (D[dp[i][j-]] < D[dp[i+(<<(j-))][j-]])
dp[i][j] = dp[i][j-];
else
dp[i][j] = dp[i+(<<(j-))][j-];
}
}
} int RMQ(int l, int r) {
if (l > r)
swap(l, r); int k = ; while ((<<(k+)) <= r-l+)
++k; if (D[dp[l][k]] < D[dp[r-(<<k)+][k]])
return V[dp[l][k]];
else
return V[dp[r-(<<k)+][k]];
} void init() {
dfs_clock = top = block = ;
memset(pre, , sizeof(pre));
memset(bn, , sizeof(bn)); rep(i, , n+) {
if (!pre[i])
tarjan(i);
} l = ;
memset(head, -, sizeof(head));
memset(link2, -, sizeof(link2));
memset(deg, , sizeof(deg));
memset(dis, , sizeof(dis));
rep(i, , n+) {
int bv = bn[i];
int bu = bn[link[i]];
if (bu == bv) {
int fx = find(link[i]);
int fy = find(i);
if (fx != fy) {
fa[fy] = fx;
dis[fy] = dis[link[i]] + ;
}
} else {
addEdge(bu, bv);
++deg[bv];
if (C[bu] > ) {
link2[bv] = link[i];
}
}
} rep(i, , block+) {
if (deg[i] == )
addEdge(, i);
} // init RMQ
top = ;
dfs(, );
RMQ_init();
} void solve(int u, int v) {
if (u == v) {
puts("0 0");
return ;
} int bu = bn[u];
int bv = bn[v];
int lca = RMQ(beg[bu], beg[bv]); #ifndef ONLINE_JUDGE
printf("bu = %d, bv = %d, lca = %d\n", bu, bv, lca);
#endif if (lca == ) {
puts("-1 -1");
return ;
} if (C[lca] == ) {
printf("%d %d\n", deep[bu]-deep[lca], deep[bv]-deep[lca]);
return ;
} int u2v, v2u;
int du, dv; if (bu == bv) {
du = dv = ;
find(u);
find(v); if (dis[u] < dis[v]) {
u2v = C[bu] + dis[u] - dis[v];
v2u = dis[v] - dis[u];
} else {
u2v = dis[u] - dis[v];
v2u = C[bv] + dis[v] - dis[u];
} } else { du = deep[bu] - deep[lca];
dv = deep[bv] - deep[lca]; int uu = link2[bu]==- ? u:link2[bu];
int vv = link2[bv]==- ? v:link2[bv]; find(uu);
find(vv); #ifndef ONLINE_JUDGE
// printf("uu=%d, duu=%d, vv=%d, dvv=%d\n", uu, dis[uu], vv, dis[vv]);
#endif
if (dis[uu] < dis[vv]) {
u2v = C[lca] + dis[uu] - dis[vv];
v2u = dis[vv] - dis[uu];
} else {
u2v = dis[uu] - dis[vv];
v2u = C[lca] + dis[vv] - dis[uu];
}
} #ifndef ONLINE_JUDGE
printf("du=%d, dv=%d, u2v=%d, v2u=%d\n", du,dv,u2v,v2u);
#endif
if (max(u2v+du, dv) < max(v2u+dv, du)) {
printf("%d %d\n", u2v+du, dv);
} else if (max(u2v+du, dv) > max(v2u+dv, du)) {
printf("%d %d\n", du, v2u+dv);
} else {
if (min(u2v+du, dv) < min(v2u+dv, du)) {
printf("%d %d\n", u2v+du, dv);
} else if (min(u2v+du, dv) > min(v2u+dv, du)) {
printf("%d %d\n", du, v2u+dv);
} else {
printf("%d %d\n", max(u2v+du, dv), min(u2v+du, dv));
}
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int q;
int u, v; while (scanf("%d %d", &n, &q)!=EOF) {
rep(i, , n+) {
fa[i] = i;
scanf("%d", &link[i]);
}
init();
while (q--) {
scanf("%d %d", &u, &v);
solve(u, v);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据生成器。
from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 10
bound = 5*10**5
for tt in xrange(t):
n = randint(bound/10, bound)
q = randint(bound/10, bound)
fout.write("%d %d\n" % (n, q))
dataList = []
for i in xrange(n):
x = randint(1, n)
dataList.append(x)
fout.write(" ".join(map(str, dataList)) + "\n")
for i in xrange(q):
u = randint(1, n)
v = randint(1, n)
fout.write("%d %d\n" % (u, v)) def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()