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(); } }