Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

模拟树结构,不知道为什么,总是TLE……

Posted by martinblack954 at 2009-08-24 19:39:08 on Problem 3321
#include "stdio.h"
#define M 110004

struct line {
    int a, b, next;
} all[M * 2];

struct fork {
    int r, num, t;
} fo[M];

int a[M], u;

void make(int x) {
    int i;
    fo[x].t = 1;
    fo[x].num = 1;
    for (i = a[x]; i != -1; i = all[i].next) {
        if(all[i].b!=fo[x].r)
        {
            fo[all[i].b].r = x;
            make(all[i].b);
        }
    }
    fo[fo[x].r].num += fo[x].num;
}

void in(int x, int c) {
    //fo[x].t+=c;
    fo[x].num += c;
    if (fo[x].r != 0)
        in(fo[x].r, c);
}

int main() {
    int i, m, n, x, y;
    char ss[5];
    while (scanf("%d", &n) > 0)
    //scanf("%d",&n);
    {   for (i = 1; i <= n; i++) {
            a[i] = -1;
        }
        u = 0;
        for (i = 0; i < n - 1; i++) {
            scanf("%d%d", &x, &y);
            all[u].a = x;
            all[u].b = y;
            all[u].next = a[x];
            a[x] = u;
            u++;
            all[u].a = y;
            all[u].b = x;
            all[u].next = a[y];
            a[y] = u;
            u++;
        }
        fo[1].r = 0;
        make(1);
        scanf("%d", &m);
        for (i = 0; i < m; i++) {
            scanf("%s%d", ss, &x);
            if (ss[0] == 'Q')
                printf("%d\n", fo[x].num);
            else {
                if (fo[x].t) {
                    fo[x].t = 0;
                    in(x, -1);
                } else {
                    fo[x].t = 1;
                    in(x, 1);
                }
            }
        }
    }
    return 0;
}


总体思路是:先用一个邻接表把“图”存下来,然后dfs将每个fork连接起来,里面的r表示该结点的根。对于每一个Q,直接访问结点即可,时间为O(1);而对于每一个C,通过in函数,沿着路径向根修改“拥有的苹果”值,按理说时间是O(lgn)。
按理说,如果是in函数卡时间的话,树状结构本来就是链型,变成O(n)一个C的话,那线段树和树状数组应该也会…………

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator