BZOJ4568: [Scoi2016]幸运数字
线性基 倍增 暴力    2016-10-12 21:21:27    154    0    0
jszyxw   线性基 倍增 暴力

4568: [Scoi2016]幸运数字

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 634  Solved: 249
[Submit][Status][Discuss]

Description

A 国共有 n 座城市,这些城市由 n-1 条道路相连,使得任意两座城市可以互达,且路径唯一。每座城市都有一个
幸运数字,以纪念碑的形式矗立在这座城市的正中心,作为城市的象征。一些旅行者希望游览 A 国。旅行者计划
乘飞机降落在 x 号城市,沿着 x 号城市到 y 号城市之间那条唯一的路径游览,最终从 y 城市起飞离开 A 国。
在经过每一座城市时,游览者就会有机会与这座城市的幸运数字拍照,从而将这份幸运保存到自己身上。然而,幸
运是不能简单叠加的,这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如,
游览者拍了 3 张照片,幸运值分别是 5,7,11,那么最终保留在自己身上的幸运值就是 9(5 xor 7 xor 11)。
有些聪明的游览者发现,只要选择性地进行拍照,便能获得更大的幸运值。例如在上述三个幸运值中,只选择 5 
和 11 ,可以保留的幸运值为 14 。现在,一些游览者找到了聪明的你,希望你帮他们计算出在他们的行程安排中
可以保留的最大幸运值是多少。
 

Input

第一行包含 2 个正整数 n ,q,分别表示城市的数量和旅行者数量。第二行包含 n 个非负整数,其中第 i 个整
数 Gi 表示 i 号城市的幸运值。随后 n-1 行,每行包含两个正整数 x ,y,表示 x 号城市和 y 号城市之间有一
条道路相连。随后 q 行,每行包含两个正整数 x ,y,表示这名旅行者的旅行计划是从 x 号城市到 y 号城市。N
<=20000,Q<=200000,Gi<=2^60
 

Output

 输出需要包含 q 行,每行包含 1 个非负整数,表示这名旅行者可以保留的最大幸运值。

 

Sample Input

4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

Sample Output

14
11

Solution

N≤20000..

倍增+暴力合并线性基

时间复杂度O(NlogN* 60 * 60)..看起来T飞了..

但是好像达不到上界?

于是就A掉了...2333

 

/*{{{*/
#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }
 
template <class T> T &read(T &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}
 
template <class T> void write(T x, char p = '\n') 
{
    register T tmp = 1;
    if (x < 0) putchar('-'), x = -x;
    while (x / tmp > 9) tmp *= 10;
    while (tmp) { putchar(x / tmp + 48); x -= x / tmp * tmp; tmp /= 10; }
    putchar(p);
}
/*}}}*/
 
const int mo = 1000000007;
const int oo = 0x3f3f3f3f;
const int maxn = 20000 + 5;
const int lg = 16;
const int size = 60 + 5;

int st[maxn], cnte;
struct edge { int to, next; } e[maxn << 1];

void addedge(int u, int v)
{
    e[++ cnte] = {v, st[u]}; st[u] = cnte;
}

long long S[size << 1];

struct gay {

    int tot;
    long long array[size];

    gay() { tot = 0; }

    void init(long long x) { array[tot = 1] = x; }

    void merge(const gay &a, const gay &b)
    {
        int top = 0;

        for (int i = 1; i <= a.tot; ++ i) S[++ top] = a.array[i];
        for (int i = 1; i <= b.tot; ++ i) S[++ top] = b.array[i];

        tot = 0;
        for (register long long j = 1ll << 60; j; j >>= 1) {
            int flag = 0;
            for (int i = tot + 1; i <= top; ++ i)
                if (S[i] & j) {
                    flag = i;
                    break;
                }
            if (!flag) continue;
            swap(S[++ tot], S[flag]);
            for (int i = 1; i <= top; ++ i)
                if (S[i] & j && i != tot)
                    S[i] ^= S[tot];
        }

        memcpy(array, S, (tot + 1) * 8);
    }

    long long count()
    {
        long long ret = 0;
        for (int i = 1; i <= tot; ++ i) {
            ret ^= array[i];
        }
        return ret;
    }

} ;
 
int n;
int q;
int dep[maxn];
int fa[maxn][lg];
int Log[maxn];
gay A, B, C;
gay a[maxn][lg];

void dfs(int x, int Fa)
{
    dep[x] = dep[Fa] + 1;
    fa[x][0] = Fa;
    for (int i = 1; i < lg; ++ i) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        a[x][i].merge(a[x][i - 1], a[fa[x][i - 1]][i - 1]);
    }
    for (int i = st[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != Fa)
            dfs(v, x);
    }
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);

    int k = dep[x] - dep[y];

    for (int i = lg - 1; ~i; -- i) {
        if (k & (1 << i))
            x = fa[x][i];
    }

    if (x == y) return x;
    
    for (int i = lg - 1; ~i; -- i) {
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }

    return fa[x][0];
}

int getfa(int x, const int &k)
{
    for (int i = 0; i < lg; ++ i) {
        if (k & (1 << i))
            x = fa[x][i];
    }
    return x;
}

void query(int x, int y)
{
    int lca = LCA(x, y);
    int dx = dep[x] - dep[lca] + 1;
    int dy = dep[y] - dep[lca] + 1;

    A.merge(a[x][Log[dx]], a[getfa(x, dx - (1 << Log[dx]))][Log[dx]]);
    B.merge(a[y][Log[dy]], a[getfa(y, dy - (1 << Log[dy]))][Log[dy]]);
    C.merge(A, B);

    write(C.count());
}

void exec() 
{
    read(n);
    read(q);

    Log[1] = 0;
    for (int i = 2; i <= n; ++ i) {
        Log[i] = Log[i >> 1] + 1;
    }

    for (int i = 1; i <= n; ++ i) {
        long long x;
        a[i][0].init(read(x));
    }

    for (int i = 1; i < n; ++ i) {
        int u, v;
        read(u);
        read(v);
        addedge(u, v);
        addedge(v, u);
    }

    dfs(1, 0);

    while (q --) {
        int x, y;
        read(x); read(y);
        query(x, y);
    }
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r")) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }
 
    exec();

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/


BZOJ2001: [Hnoi2010]City 城市建设
154 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航