HDOJ 4274 Spy's Work DFS
12026 ワード
DFSは各ノードが表す範囲を維持する....
Spy’s Work
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1382 Accepted Submission(s): 438
Problem Description I’m a manager of a large trading company, called ACM, and responsible for the market research. Recently, another trading company, called ICPC, is set up suddenly. It’s obvious that we are the competitor to each other now! To get some information about ICPC, I have learned a lot about it. ICPC has N staffs now (numbered from 1 to N, and boss is 1), and anybody has at most one superior. To increase the efficiency of the whole company, the company contains N departments and the ith department is led by the ith staff. All subordinates of the ith staff are also belong to the ith department. Last week, we hire a spy stealing into ICPC to get some information about salaries of staffs. Not getting the detail about each one, the spy only gets some information about some departments: the sum of the salaries of staff s working for the ith department is less than (more than or equal to) w. Although the some inaccurate information, we can also get some important intelligence from it. Now I only concerned about whether the spy is telling a lie to us, that is to say, there will be some conflicts in the information. So I invite you, the talented programmer, to help me check the correction of the information. Pay attention, my dear friend, each staff of ICPC will always get a salary even if it just 1 dollar!
Input There are multiple test cases. The first line is an integer N. (1 <= N <= 10,000) Each line i from 2 to N lines contains an integer x indicating the xth staff is the ith staff’s superior( x or =) w), indicating the sum of the xth department is less than(more than or equal to) w (1 <= w <=100,000,000)
Output For each test case, output “True” if the information has no confliction; otherwise output “Lie”.
Source 2012 ACM/ICPC Asia Regional Changchun Online
Spy’s Work
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1382 Accepted Submission(s): 438
Problem Description I’m a manager of a large trading company, called ACM, and responsible for the market research. Recently, another trading company, called ICPC, is set up suddenly. It’s obvious that we are the competitor to each other now! To get some information about ICPC, I have learned a lot about it. ICPC has N staffs now (numbered from 1 to N, and boss is 1), and anybody has at most one superior. To increase the efficiency of the whole company, the company contains N departments and the ith department is led by the ith staff. All subordinates of the ith staff are also belong to the ith department. Last week, we hire a spy stealing into ICPC to get some information about salaries of staffs. Not getting the detail about each one, the spy only gets some information about some departments: the sum of the salaries of staff s working for the ith department is less than (more than or equal to) w. Although the some inaccurate information, we can also get some important intelligence from it. Now I only concerned about whether the spy is telling a lie to us, that is to say, there will be some conflicts in the information. So I invite you, the talented programmer, to help me check the correction of the information. Pay attention, my dear friend, each staff of ICPC will always get a salary even if it just 1 dollar!
Input There are multiple test cases. The first line is an integer N. (1 <= N <= 10,000) Each line i from 2 to N lines contains an integer x indicating the xth staff is the ith staff’s superior( x or =) w), indicating the sum of the xth department is less than(more than or equal to) w (1 <= w <=100,000,000)
Output For each test case, output “True” if the information has no confliction; otherwise output “Lie”.
Sample Input
5
1
1
3
3
3
1 < 6
3 = 4
2 = 2
5
1
1
3
3
3
1 > 5
3 = 4
2 = 2
Sample Output
Lie
TrueSource 2012 ACM/ICPC Asia Regional Changchun Online
/* *********************************************** Author :CKboss Created Time :2015 09 07 15 45 20 File Name :H.cpp ************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
const int maxn=10100;
const LL INF=0x3f3f3f3f3f3f3f3f;
struct Edge
{
int to,next;
}edge[maxn*3];
int Adj[maxn],Size;
void init()
{
memset(Adj,-1,sizeof(Adj)); Size=0;
}
void Add_Edge(int u,int v)
{
edge[Size].to=v;
edge[Size].next=Adj[u];
Adj[u]=Size++;
}
int n,m;
int qid[maxn];
char cmd[maxn][20];
int cha[maxn];
LL range[maxn][2];
bool flag;
bool jiao(LL a,LL b,LL c,LL d)
{
return ((a>=c&&a<=d)||(b>=c&&b<=d)||(c>=a&&c<=b)||(d>=a&&d<=b));
}
void dfs(int u)
{
if(flag==false) return ;
LL low=1,high=10000000000000LL;
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
dfs(v);
low+=range[v][0];
high+=range[v][1];
}
if(range[u][0]==0) range[u][0]=low;
if(range[u][1]==INF) range[u][1]=high;
if(jiao(low,high,range[u][0],range[u][1])
&&(range[u][0]<=range[u][1]))
{
/// ok
if(low>range[u][0])
range[u][0]=low;
if(high<range[u][1])
range[u][1]=high;
}
else flag=false;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d",&n)!=EOF)
{
init();
memset(qid,-1,sizeof(qid));
for(int i=2,x;i<=n;i++)
{
scanf("%d",&x);
Add_Edge(x,i);
range[i][0]=0; range[i][1]=INF;
}
range[1][0]=0; range[1][1]=INF;
flag=true;
scanf("%d",&m);
for(int i=1,x;i<=m;i++)
{
scanf("%d%s%d",&x,cmd[i],cha+i);
if(qid[x]==-1)
{
qid[x]=i;
if(cmd[i][0]=='<')
range[x][1]=cha[i]-1;
else if(cmd[i][0]=='>')
range[x][0]=cha[i]+1;
else if(cmd[i][0]=='=')
range[x][0]=range[x][1]=cha[i];
}
else
{
if(cmd[i][0]=='<')
{
if(cha[i]-1<range[x][1])
range[x][1]=cha[i]-1;
}
else if(cmd[i][0]=='>')
{
if(cha[i]+1>range[x][0])
range[x][0]=cha[i]+1;
}
else if(cmd[i][0]=='=')
{
if(cha[i]>=range[x][0]&&cha[i]<=range[x][1])
range[x][0]=range[x][1]=cha[i];
else flag=false;
}
}
if(range[x][0]>range[x][1]) flag=false;
}
//cout<<"flag: "<<flag<<endl;
dfs(1);
/* for(int i=1;i<=n;i++) { printf("%d: %lld <---> %lld
",i,range[i][0],range[i][1]); } */
if(flag==false) puts("Lie");
else puts("True");
}
return 0;
}