比赛 |
20160909 |
评测结果 |
AAWTAWT |
题目名称 |
基本的图问题 |
最终得分 |
42 |
用户昵称 |
悟理 |
运行时间 |
2.136 s |
代码语言 |
C++ |
内存使用 |
1.05 MiB |
提交时间 |
2016-09-09 21:50:52 |
显示代码纯文本
#include <fstream>
using namespace std;
const int MAX_VALUE = 100001;
int Data[MAX_VALUE];
int FatherOf[MAX_VALUE];
//int Min[MAX_VALUE];
//int Max[MAX_VALUE];
inline int GetInt(FILE *fin)
{
int num = 0,flag = 0;
char ch;
ch = fgetc(fin);
while(' ' == ch || '\n' == ch)
ch = fgetc(fin);
if ('-' == ch)
{
flag = 1;
ch = fgetc(fin);
}
while('0' <= ch && ch <= '9')
{
num = (num << 3) + (num << 1) + ch - '0';
ch = fgetc(fin);
}
if (flag)
return -num;
else
return num;
}
inline int FindFather(int x)
{
if (FatherOf[x] != x)
FatherOf[x] = FindFather(FatherOf[x]);
return FatherOf[x];
}
inline void Merge(int x,int y)
{
FatherOf[FindFather(y)] = FindFather(x);
}
int Main()
{
FILE *fin = fopen("basicgraph.in","r");
FILE *fout = fopen("basicgraph.out","w");
int DataSize = GetInt(fin);
//int p_max = 0,p_min = 0;
Data[1] = GetInt(fin);
FatherOf[1] = 1;
Data[0] = 0;
for (int i = 2;i <= DataSize;++i)
{
Data[i] = GetInt(fin);
/*if (Data[i - 2] > Data[i - 1] && Data[i - 1] < Data[i])
{
Min[p_min] = i - 1;
++p_min;
}
else if (Data[i - 2] < Data[i - 1] && Data[i - 1] > Data[i])
{
Max[p_max] = i - 1;
++p_max;
}*/
FatherOf[i] = i;
}
int DataSize_L = GetInt(fin);
int left,right,max = 0,min = MAX_VALUE;
for (int i = 1;i <= DataSize_L;++i)
{
left = GetInt(fin);
right = GetInt(fin);
/*for (int j = 0;j < p_max;++j)
if (left <= Max[j] && Max[j] <= right)
if (Max[j] > max)
max = Max[j];
for (int j = 0;j < p_min;++j)
if (left <= Min[j] && Min[j] <= right)
if (Min[j] < min)
min = Min[j];*/
for (int j = left;j <= right;++j)
{
if (Data[j] > max)
max = Data[j];
if (Data[j] < min)
min = Data[j];
}
Merge(max,min);
}
int DataSize_Q = GetInt(fin);
int x,y;
for (int i = 1;i <= DataSize_Q;++i)
{
x = GetInt(fin);
y = GetInt(fin);
if (FindFather(x) == FindFather(y))
fprintf(fout,"YES\n");
else
fprintf(fout,"NO\n");
}
fclose(fin);
fclose(fout);
return 0;
}
int asd = Main();
int main(){;}