BZOJ4690: Never Wait for Weights

Time Limit: 15 Sec  Memory Limit: 256 MB

Description

在实验室中,Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时,使用天平能比使用

弹簧秤得到更精确的结果,所以他只使用天平来测得一些样品的重量差。他偶尔会被询问一些样品的重量差,而他

能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于他所在处理的测量数据是巨大的,所以他

希望你能写个程序帮他处理数据和回答问题。

Input

输入包含多组测试数据。每组数据第一行包含两个整数 N 和 M ,其中 N 表示样品的数量,

样品从 1 到 N 标号,满足 2≤N≤100000 。

接下来 M 行,每行包括一个测量结果或者询问,按时间顺序给出,满足 1≤M≤100000 。

一个测量结果被格式化为 ! a b w ,表示第 a 个样品比第 b 个样品轻 w 个单位重量

满足 a≠b,0≤w≤1000000 ,且任意的测试结果互不矛盾。

一个询问被格式化为 ? a b ,表示询问第 a 个样品比第 b 个样品轻多少个单位重量,满足 a≠b 。

输入以两个零作为结束。

Output

对于每个询问输出一行,如果能回答问题,则输出问题的答案,你可以认为答案的绝对值不超过 1000000

否则输出 UNKNOWN ,表示不能回答问题。

Sample Input

2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0

Sample Output

1
-1
UNKNOWN
100
200

-50


/**************************************************************

    Problem: 4690

    User: ictsing

    Language: C++

    Result: Accepted

    Time:620 ms

    Memory:4076 kb

****************************************************************/

 

//BZOJ4690 Never Wait for Weights

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int mt = 100000+5;

int f[mt],v[mt];

char op[2];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int findf(int x)

{

    if(f[x]==x) return x;

    int ff=findf(f[x]);

    v[x]+=v[f[x]];

    f[x]=ff;

    return f[x];

}

int main()

{

    int n,m;

    while(true)

    {

        n=read(),m=read();

        if(n==0&&m==0)

            break;

        for(int i=1;i<=n;i++)

            f[i]=i,v[i]=0;

        for(int i=1;i<=m;i++)

        {

            scanf("%s",op);

            if(op[0]=='!')

            {

                int a=read(),b=read(),w=read();

                int fa=findf(a),fb=findf(b);

                if(fa!=fb)

                {

                    f[fa]=fb;

                    v[fa]=v[b]+w-v[a];

                }

            }

            else

            {

                int a=read(),b=read();

                int fa=findf(a),fb=findf(b);

                if(fa!=fb)

                {

                    puts("UNKNOWN");

                }

                else printf("%d\n",v[a]-v[b]);

            }

        }

    }

    return 0;

}

 


评论

热度(5)