Submission #19420558

---

Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {

	static long mod = 1000000007;
	static int inf = Integer.MAX_VALUE-1;
	static long infL = 0xfffffffffffffffL;

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		int[] p = new int[n];
		p[0] = -1;
		for(int i = 1; i < n; i++) {
			p[i] = sc.nextInt()-1;
		}
		int[] x = new int[n];
		for(int i = 0; i < n; i++) {
			x[i] = sc.nextInt();
		}

		boolean[] f = new boolean[n];
		int[][] dp = new int[n][5001];
		for(int i = 0; i < n-1; i++) {
			Arrays.fill(dp[i], -1);
		}

		for(int i = n-1; i > 0; i--) {
			int o = p[i];



			if(!f[i]) {

				if(!f[o]) {
					f[o] = true;
					dp[o][x[i]] = 0;
					dp[o][0] = x[i];
				}else {
					for(int j = 5000; j >= 0; j--) {
						if(dp[o][j] == -1)
							continue;

						int tmp = dp[o][j];
						if(tmp <= 5000)
							dp[o][tmp] = x[i];
						if(x[i]+tmp <= 5000)
							dp[o][x[i]+tmp] = 0;

						dp[o][j] = 0;
					}
				}

			}else {
				int min = 10000;
				for(int j = 0; j <= x[i]; j++) {
					if(dp[i][j] != -1 && min > dp[i][j])
						min = dp[i][j];
				}
				if(min == 10000) {
					System.out.println("IMPOSSIBLE");
					return;
				}

				if(!f[o]) {
					f[o] = true;

					dp[o][x[i]] = min;
					dp[o][min] = x[i];

				}else {

					for(int j = 5000; j >= 0; j--) {
						if(dp[o][j] == -1) {
							dp[o][j] = -1;
							continue;
						}

						int tmp = dp[o][j];
						if(min+tmp <= 5000)
							dp[o][min+tmp] = x[i];
						if(x[i]+tmp <= 5000)
							dp[o][x[i]+tmp] = min;

						dp[o][j] = -1;
					}
				}
			}
		}

		String ans = "IMPOSSIBLE";
		for(int i = 0; i <= x[0]; i++) {
			if(dp[0][i] != -1) {
				ans = "POSSIBLE";
				break;
			}
		}

		System.out.println(ans);

	}

	private static int binarySearch2D(long key, long[][] ps, int ind, int fromIndex, int toIndex) {

		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
		int mid = (low + high) >>> 1;
		long midVal = ps[mid][ind];

		if (midVal < key)
			low = mid + 1;
		else if (midVal > key)
			high = mid - 1;
		else
			return mid; // key found
		}
		return -(low + 1);  // key not found.
	}
}

class Pair{
	int v;
	long h;

	public Pair(int v, long h) {
		this.v = v;
		this.h = h;
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in2) {
		// TODO 自動生成されたコンストラクター・スタブ
	}
	private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Submission Info

Judge Result