某岛

… : "…アッカリ～ン . .. . " .. .

September 22, 2011

UVa 11994. Happy Painting!

Brief description :

… 给定一棵 N 个结点的有根树森林，边上有一个颜色，需要支持下面这 3 个操作。

Query(x, y) 如果 x 和 y 在同一棵子树中，则询问路径上边的数目、和颜色的种类数。
Paint(x, y, c) 如果 x 和 y 在同一棵子树中，则将经过的路径上所有边染色为 c。
Link(x, y, c) 如果 x 和 y 在同一个子树中，且 x 不为 y 的祖先，那么切断 x 同其父亲的联系，之后用一条颜色为 c 的边连接 x、y。

(.. N = 50, 000 ..)

Analysis :

.. LRJ Preset 3 ..( 介于 UVa 经常无限重定向。。可以用 Virtual Judge 做 VPN .. .)

… 显然这个题对我来说已经变成可做题了。。虽然当时就只有跳过的份了。。
（。。。LCA 的地方 WA 了一次。。还有 mask 的地方 WA 了几次。。。）

/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)

#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)
#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)
#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)
#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)
#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define BSC(A, X) find(ALL(A), X) // != A.end()
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

#define Rush int T____; RD(T____); DO(T____)
#pragma comment(linker, "/STACK:36777216")
#pragma GCC optimize ("O2")
#define Ruby system("ruby main.rb")
#define Haskell system("runghc main.hs")
#define Pascal system("fpc main.pas")

/** I/O Accelerator **/

/* ... :" We are I/O Accelerator ... Use us at your own risk ;) ... " .. */

template<class T> inline void RD(T &);
template<class T> inline void OT(const T &);

inline int RD(){ int x; RD(x); return x;}
template<class T> inline T& _RD(T &x){ RD(x); return x;}

template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);}
template<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}


/** Add - On **/

// <<= ` 0. Daily Use .,

template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
int Ceil(int x, int y){return (x - 1) / y + 1;}

// <<= ` 1. Bitwise Operation .,

inline bool _1(int x, int i){return x & 1<<i;}
inline int _1(int i){return 1<<i;}
inline int _U(int i){return _1(i) - 1;};

inline int count_bits(int x){
    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
    return x;
}

template<class T> inline T low_bit(T x) {
    return x & -x;
}

template<class T> inline T high_bit(T x) {
    T p = low_bit(x);
    while (p != x) x -= p, p = low_bit(x);
    return p;
}

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    //scanf("%d", &x);
    char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';

}

inline void OT(int a, int b){
    printf("%d %d\n", a, b);
}

/* .................................................................................................................................. */

const int N = 50009;

int l[N], r[N], p[N], sz[N], color[N], delay[N], mask[N]; bool rt[N];
int n, m;

#define lx l[x]
#define rx r[x]

inline void Paint(int x, int c){
    if (x == 0) return;
    color[x] = delay[x] = mask[x] = c;
}

inline void Release(int x){
    if (x == 0 || !delay[x]) return;
    Paint(lx, delay[x]), Paint(rx, delay[x]);
    delay[x] = 0;
}

inline void Update(int x){
    sz[x] = sz[lx] + sz[rx] + 1;
    mask[x] = color[x] | mask[lx] | mask[rx];
}

inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}

inline void Rotate(int x){
    int y = p[x], z = p[y];

    if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);
    else p[x] = z;

    Release(y), Release(x);

    if (x == l[y]) Set(l, y, rx), Set(r, x, y);
    else Set(r, y, lx), Set(l, x, y);

    if (rt[y]) rt[y] = false, rt[x] = true;

    Update(y);
}

inline void Splay(int x){
    while (!rt[x]) Rotate(x);
}

int Access(int x){
    int y = 0; do{
        Splay(x), Release(x);
        rt[rx] = true, rt[rx = y] = false; Update(x);
        x = p[y = x];
    } while (x);
    return y;
}

inline int Root(int x){
    for (x = Access(x); lx ; x = lx);
    return x;
}

inline int Depth(int x){
    return sz[Access(x)];
}

inline int Lca(int x, int y){
    int lca; Access(y); y = 0; do{
        Splay(x), Release(x); if (!p[x]) lca = x;
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
    return lca;
}


// Public :

void Query(int x, int y){

    if (x == y || Root(x) != Root(y)){
        OT(0, 0);
        return;
    }

    Access(y); y = 0; do{
        Splay(x), Release(x); if (!p[x]) OT(sz[rx] + sz[y], count_bits(mask[rx] | mask[y]));
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
}

void Paint(int x, int y, int c){

    if (Root(x) != Root(y)) return;

    c = _1(c - 1), Access(y); y = 0; do{
        Splay(x), Release(x); if (!p[x]) Paint(rx, c), Paint(y, c);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
}

void Link(int x, int y, int c){

    if (x == y || Root(x) == Root(y) && Lca(x, y) == x) return;

    c = _1(c - 1), Access(x), Splay(x), rt[lx] = true;
    lx = p[lx] = 0, p[x] = y, Paint(x, c), Update(x);
    Access(x);
}

int main(){

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    while (scanf("%d %d", &n, &m) != EOF){

        // Initializing Phase ...

        REP_1(i, n) sz[i] = 1, rt[i] = true, RD(p[i]);

        REP_1(i, n) color[i] = mask[i] = _1(RD() - 1);

        // Interaction Phase ...

        int op, a, b, c;

        DO(m){
            RD(op); if (op == 3) RD(a, b), Query(a, b);
            else if (op == 2) RD(a, b, c), Paint(a, b, c);
            else RD(a, b, c), Link(a, b, c);
        }

        // Rececling ....

        RST(p, l, r, delay);
    }
}

External link :

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=18699
http://blog.renren.com/blog/247466695/722043176

Posted by xiaodao
Category: UVa

Archives

open all | close all
Tweets by MinakoOikawa
Blogroll
- Alca
- Amber
- AyakaNeko
- Belleve Invis
- billchen
- Chensiting123
- Edward_mj
- Fotile96
- hanaki
- Hlworld
- Kuangbin
- laike9m
- Liyaos
- Lwins
- LYPenny
- Mato 完整版
- Mikeni2006
- Miz.Reso
- Mzry
- Nagatsuki
- Neko13
- Oneplus
- Orpinex
- PaperNeko
- rqy
- Rukata
- Seter
- Sevenkplus
- Sevenzero
- Shirleycrow
- Shisoft
- sukitsuki
- Vfleaking
- wangzhpp
- Watashi
- WJMZBMR
- Wywcgs
- XadillaX
- Yangzhe
- 三途川玉子
Links
- ACM_DIY
- ACM/ICPC 信息站
- Ch_g
- Drcrow
- Fanhq666
- Figo
- Hust Virtual Judge
- Not "Not Even Wrong"
- Oimaster
- Robin
- Sillycross
- Vani
- zjut_DD
- 白衣少年
- 衡Ⅷ
Myself
- About.me
- Q-Zone
Project
- Vijos
- 梦日记中文站

某岛

UVa 11994. Happy Painting!

Brief description :

Analysis :

External link :

Archives

Blogroll

Links

Myself

Project