首页 > 代码库 > POJ 1470 Closest Common Ancestors 离线LCA
POJ 1470 Closest Common Ancestors 离线LCA
实测查询量大概是25W左右,离线搞比较快.
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;const int maxn = 1000;struct Edge { int u, v, id; Edge(int u, int v, int id = 0): u(u), v(v), id(id) {}};vector<Edge> e[maxn], q[maxn];int n, fa[maxn], ans[260000], col[maxn], pfa[maxn];map<int, int> mp;int getfa(int u) { return fa[u] == u ? u : fa[u] = getfa(fa[u]);}void dfs(int now) { int qsize = q[now].size(); col[now] = 1; for(int i = 0; i < qsize; i++) if(ans[q[now][i].id] == -1) { int v = q[now][i].v; if(col[v] != 0) ans[q[now][i].id] = getfa(v); } int esize = e[now].size(); for(int i = 0; i < esize; i++) { int v = e[now][i].v; dfs(v); fa[v] = now; }}int main() { while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i++) { e[i].clear(); q[i].clear(); fa[i] = i; col[i] = 0; } memset(pfa, -1, sizeof(pfa)); for(int i = 1; i <= n; i++) { int now, cnt; scanf("%d:(%d)", &now, &cnt); for(int j = 0; j < cnt; j++) { int tmp; scanf("%d", &tmp); e[now].push_back(Edge(now, tmp)); pfa[tmp] = now; } } int qcnt; scanf("%d", &qcnt); char kk; memset(ans, -1, sizeof(ans)); for(int i = 1; i <= qcnt; i++) { int a, b; scanf(" %c%d %d%c", &kk, &a, &b, &kk); q[a].push_back(Edge(a, b, i)); q[b].push_back(Edge(b, a, i)); } int root; for(int i = 1; i <= n; i++) if(pfa[i] == -1) root = i; dfs(root); mp.clear(); for(int i = 1; i <= qcnt; i++) mp[ans[i]]++; for(map<int, int>::iterator i = mp.begin(); i != mp.end(); i++) { cout << i->first << ":" << i->second << endl; } } return 0;}
POJ 1470 Closest Common Ancestors 离线LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。