Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-09

PKU 3764 -- The xor-longest Path

| 09:57 | PKU 3764 -- The xor-longest Path - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3764 -- The xor-longest Path - Wrong Answer -- japlj PKU 3764 -- The xor-longest Path - Wrong Answer -- japlj のブックマークコメント

len[x] := 頂点 0 から頂点 x までの path の xor-length

とすると

頂点 i から頂点 j までの path の xor-length = len[i] xor len[j]

が成り立つので xor が最大になる組を見つける問題になる。

組のうち片方を決めて、できるだけ高いビットが1になるようにもう片方を選んでいく。

Trieを使うとその操作が O(log len[x]の最大値) で出来るので合わせて O(n log W) で出来る。(W = 枝コストの最大値)

O(n log^2 W) などを落とすためにTLEが厳しめらしいので木を vector とかで持っていると push_back の時間だけでTLEしたりする。


#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

struct node { int v, w; node* p; } *adj[100000], pool[200000];
int len[100000], trie[3100000][2];

void dfs(int u, int p, int l)
{
  len[u] = l;
  for(node *x=adj[u]; x; x=x->p)
    if(x->v != p) dfs(x->v, u, l^x->w);
}

int main()
{
  int n;
  while(~scanf("%d", &n)) {
    int D = 0, E = 0;
    memset(adj, 0, sizeof(adj));
    for(int i=0; i<n-1; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      pool[E].v=v; pool[E].w=w; pool[E].p=adj[u]; adj[u]=&pool[E++];
      pool[E].v=u; pool[E].w=w; pool[E].p=adj[v]; adj[v]=&pool[E++];
      D = max(D, w);
    }
    D = (int)(log((double)D)/log(2.));
    dfs(0, -1, 0);
    int sol = 0, T = 1;
    memset(trie, -1, sizeof(int) * n * 31 * 2);
    for(int i=0; i<n; ++i) {
      int p = 0, q = 0, v = 0;
      for(int j=D; j>=0; --j) {
	int b = !!(len[i] & (1<<j));
	if(trie[p][b] < 0) trie[p][b] = T++;
	p = trie[p][b];
	if(trie[q][1-b] < 0) q = trie[q][b];
	else { v |= 1<<j; q = trie[q][1-b]; }
      }
      sol = max(sol, v);
      if(sol == (1ll<<(D+1))-1) break;
    }
    printf("%d\n", sol);
  }
  return 0;
}

PKU 3728 -- The merchant

| 06:48 | PKU 3728 -- The merchant - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3728 -- The merchant - Wrong Answer -- japlj PKU 3728 -- The merchant - Wrong Answer -- japlj のブックマークコメント

s -> t の経路は s -> LCA(s, t) -> t に分けて考える。LCA(u, v) は u, v の最小共通先祖。

Tarjan のオフライン最小共通先祖を解くアルゴリズム中で、LCA(s, t) が分かった段階で query(s, t) の答を計算しておくとよい。

そのために、各頂点にいくつかの情報を持たせる必要がある。

頂点 v について、ある時点で union されている集合のうち最も上にいる先祖を a(v) としたときに

  • v -> a(v) の経路での最大の収益(maxprofit)
  • a(v) -> v の経路での最大の収益(maxprofit_r)
  • v -- a(v) 中の最大の商品の値段(maxcost)
  • v -- a(v) 中で最小の商品の値段(mincost)

の4つを持たせておくと、LCA(s, t)が分かった時点で query(s, t) の答は max{s.maxprofit, t.maxprofit_r, t.maxcost - s.mincost} となる。


#include<cstdio>
#include<vector>

using namespace std;

struct query_lca {
  int v;
  int query_id;
  bool u_first;
  query_lca(int a, int b, bool c)
    : v(a), query_id(b), u_first(c) { }
};
struct query_profit {
  int s, t;
  int query_id;
  query_profit(int a, int b, int c)
    : s(a), t(b), query_id(c) { }
};
struct path_info {
  int mincost, maxcost;
  int maxprofit, maxprofit_r;
  path_info(int cost=0)
    : mincost(cost), maxcost(cost), maxprofit(0), maxprofit_r(0) { }
};

int N, Q;
vector<int> adj[50000];
vector<query_lca> queries_lca[50000];
vector<query_profit> queries_profit[50000];

path_info paths[50000];
int ancestor[50000];
void init(int n) { for(int i=0; i<n; ++i) ancestor[i]=i; }
int find(int x) {
  int par = ancestor[x];
  if(x!=ancestor[x]) {
    ancestor[x]=find(ancestor[x]);
    paths[x].maxprofit = max(paths[x].maxprofit, max(paths[par].maxprofit, paths[par].maxcost-paths[x].mincost));
    paths[x].maxprofit_r = max(paths[x].maxprofit_r, max(paths[par].maxprofit_r, paths[x].maxcost-paths[par].mincost));
    paths[x].maxcost = max(paths[x].maxcost, paths[par].maxcost);
    paths[x].mincost = min(paths[x].mincost, paths[par].mincost);
  }
  return ancestor[x];
}

bool visited[50000] = {false};
int answer[50000];
void dfs(int u)
{
  visited[u] = true;
  for(int i=0; i<(int)adj[u].size(); ++i) {
    if(!visited[adj[u][i]]) {
      dfs(adj[u][i]);
      ancestor[adj[u][i]] = u;
    }
  }
  for(int i=0; i<(int)queries_lca[u].size(); ++i) {
    query_lca q = queries_lca[u][i];
    if(!visited[q.v]) continue;
    if(q.u_first) queries_profit[find(q.v)].push_back(query_profit(u, q.v, q.query_id));
    else queries_profit[find(q.v)].push_back(query_profit(q.v, u, q.query_id));
  }
  for(int i=0; i<(int)queries_profit[u].size(); ++i) {
    query_profit q = queries_profit[u][i];
    find(q.s); find(q.t);
    answer[q.query_id] = max(paths[q.s].maxprofit, max(paths[q.t].maxprofit_r, paths[q.t].maxcost-paths[q.s].mincost));
  }
}

int main()
{
  scanf("%d", &N);
  for(int i=0; i<N; ++i) {
    int c;
    scanf("%d", &c);
    paths[i] = path_info(c);
  }
  for(int i=0; i<N-1; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  scanf("%d", &Q);
  for(int i=0; i<Q; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    queries_lca[a].push_back(query_lca(b, i, true));
    queries_lca[b].push_back(query_lca(a, i, false));
  }
  init(N);
  dfs(0);
  for(int i=0; i<Q; ++i)
    printf("%d\n", answer[i]);
  return 0;
}
 |