Spy‘s Work

5
1
1
3
3
3
1 < 6
3 = 4
2 = 2

5
1
1
3
3
3
1 > 5
3 = 4
2 = 2

Lie
True

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>

using namespace std;

typedef long long ll;
const ll INF=1e16;
const int maxn=1e4+5;

struct T {
    ll l;
    ll r;
};
T range[maxn];
vector<int> g[maxn];

int n;

void inti() {
    for(int i=1; i<=n; i++) {
        g[i].clear();
        range[i].l=1;
        range[i].r=INF;
    }
}

bool dfs(int u) {
    if(g[u].size()==0)
        return true;
    ll l=1;///左区间的最小值，初始化为1，右区间不用更新
    for(int i=0; i<g[u].size(); i++) {
        int v=g[u][i];
        bool res=dfs(v);
        if(res==false)
            return false;
        l+=range[v].l;
        if(l>range[u].r)
            return false;
    }
    range[u].l=max(range[u].l,l);///更新
    return true;
}

int main() {
    while(~scanf("%d",&n)) {
        inti();
        for(int i=2; i<=n; i++) {
            int x;
            scanf("%d",&x);
            g[x].push_back(i);
        }
        int m;
        scanf("%d",&m);
        bool res=true;
        for(int i=1; i<=m; i++) {
            int ith,x;
            char c;
            scanf("%d %c %d",&ith,&c,&x);
            if(c=='=') {          ///等于的情况，左右区间都为x
                if(x<range[ith].l||x>range[ith].r)///不符合
                    res=false;
                range[ith].l=x;
                range[ith].r=x;
            } else if(c=='<') {  ///小于的情况更新有区间
                if(range[ith].l>=x)
                    res=false;
                range[ith].r=x-1;
            } else {   ///大于的情况更新左区间
                if(range[ith].r<=x)
                    res=false;
                range[ith].l=x+1;
            }
        }
        if(res) {
            res=dfs(1);
        }
        if(res==true)
            puts("True");
        else
            puts("Lie");
    }
    return 0;
}

Hdu 4274 Spy's Work

原文：http://blog.csdn.net/acm_baihuzi/article/details/47481761