ZOJ – 2615 Cells

注意数组别开太小了，代码照着训练经典打的：

#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define mp(a, b) make_pair((a), (b))
#define in  freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop  system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define pragma comment(linker, "/STACK:102400000, 102400000")
#define inf 0x0f0f0f0fusing namespace std;
typedef long long  LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii,int> VII;
typedef vector<int>:: iterator IT;
const int maxn = 20000005;
const int mxn = 300005;
int pre[maxn], post[maxn], start[mxn], c[mxn];
int n;void dfs(int root)
{
    stack<int>  S;
    S.push(root);
    pre[root] = 0;
    int dfs_clock = 0;
    while(!S.empty())
    {
        int x = S.top();
        if(pre[x])
        {
            post[x] = ++dfs_clock;
            S.pop();
            continue;
        }
        pre[x] = ++dfs_clock;
        for(int i = start[x]; i < start[x] + c[x]; i++)
            if(i < n)
            {
                pre[i] = 0;
                S.push(i);
            }
            else
            {
                pre[i] = ++dfs_clock;
                post[i] = ++dfs_clock;
            }
    }
}
int main(void)
{
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++)
    {
        printf("Case %d:\n", t);
        scanf("%d", &n);
        start[0] = 1;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &c[i]);
            if(i>0)
                start[i] = start[i-1]+c[i-1];
        }
        dfs(0);
        int m;
        scanf("%d", &m);
        while(m--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if(pre[a] < pre[b] && post[a] > post[b])
                puts("Yes");
            else puts("No");
        }
        if(t != T)
            puts("");
    }
    return 0;
}