PKU 2827 Auto-Calculation Machine

http://poj.org/problem?id=2827
長さ10^9くらいの配列があり、そのうち要素iから要素jまでの和がvであるというような情報がm個与えられる。

このとき、その情報に矛盾があればそれを検出しろといような問題

ユニオンファインドしつつ、親までの距離も管理すればいい。
i,jの順番は適当なようなので注意する必要がある。
c++だと全然間に合わせられなかったので、javaにしました。

去年のアジア大会の問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330
にかなり似てます。

import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args)
    throws IOException{
        new Main().run();
    }

    int[] ini=new int[10000];
    int[] inj=new int[10000];
    int[] inv=new int[10000];
    int[] un=new int[30000];
    Long[] di=new Long[30000];

    int find(int x){
        if(x==un[x])
            return x;
        int pp = un[x];
        int p = find(un[x]);
        di[x] += di[un[x]];
        return
            un[x] = p;
    }

    void unit(int a,int b,int x){
        int ap=find(a);
        int bp=find(b);

        un[ap] = bp;
        /*
        System.out.println(ap);
        System.out.println(b);
        System.out.println(a);
        */
        di[ap] = di[b] + x - di[a];
    }

    BufferedReader cin;
    BufferedWriter cout;

    public void run()
    throws IOException{
        cin =
            new BufferedReader(new InputStreamReader(System.in));
        cout =
            new BufferedWriter(new OutputStreamWriter(System.out));        
        int m = Integer.parseInt(cin.readLine());


        TreeSet<Integer> app = new TreeSet<Integer>();
        for(int i=0;i<m;++i){
            StringTokenizer in = new StringTokenizer(cin.readLine()," ");
            ini[i] = Integer.parseInt(in.nextToken());
            inj[i] = Integer.parseInt(in.nextToken());
            
            if(ini[i]>inj[i]){
                int tmp = ini[i];
                ini[i] = inj[i];
                inj[i] = tmp;
            }
            
            inv[i] = Integer.parseInt(in.nextToken());
            app.add(ini[i]);
            app.add(inj[i]+1);
            un[i*2]=i*2;
            un[i*2+1]=i*2+1;
            di[i*2]=0L;
            di[i*2+1]=0L;
        }

        int[] arr = new int[app.size()];
        int cnt = 0;
        for(Integer it : app){
            arr[cnt++] = it.intValue();
        }


        for(int i=0;i<m;++i){
            int a=Arrays.binarySearch(arr,ini[i]);
            int b=Arrays.binarySearch(arr,inj[i]+1);
            boolean bo = find(a) == find(b);
            if(bo &&
               di[a] - di[b] != inv[i]){
                cout.write("Bug Detected " + (di[a]-di[b]));
                cout.newLine();
            }else{
                if(!bo)
                    unit(a,b,inv[i]);
                cout.write("Accept");
                cout.newLine();
            }
            
        }
        cout.close();
    }
}