#540818 (Java21) No.899 γatheree

提出ソース

結果

問題	No.899 γatheree
ユーザー	37zigen
提出日時	2020-08-27 09:46:49
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	5,585 bytes
コンパイル時間	2,737 ms
コンパイル使用メモリ	83,184 KB
実行使用メモリ	69,720 KB
最終ジャッジ日時	2024-11-07 15:28:57
合計ジャッジ時間	24,888 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	54 ms 36,576 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	1,064 ms 69,580 KB
testcase_22	AC	1,019 ms 69,452 KB
testcase_23	AC	1,030 ms 69,720 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    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());}
}


class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	class Seg {
		int n=1;
		long[] v;
		boolean[] clear;
		final long NIL=-1;
		
		public Seg(int n_) {
			while (n<n_) n*=2;
			v=new long[2*n-1];
			clear=new boolean[2*n-1];
		}
		
		void propagate(int k) {
			if (!clear[k]) return;
			v[k]=0;
			if (2*k+1<2*n-1) {
				clear[2*k+1]=true;
				clear[2*k+2]=true;
			}
			clear[k]=false;
		}
		
		void range_clear(int a,int b) {
			range_clear(0,n,a,b,0);
		}
		
		void range_clear(int l,int r,int a,int b,int k) {
			propagate(k);
			if (r<=a||b<=l) return;
			if (a<=l&&r<=b) {
				clear[k]=true;
				propagate(k);
			} else {
				range_clear(l,(l+r)/2,a,b,2*k+1);
				range_clear((l+r)/2,r,a,b,2*k+2);
				v[k]=v[2*k+1]+v[2*k+2];
			}
		}
		
		long point_add(int a,int b,long add) {
			return point_add(0,n,a,b,0,add);
		}
		
		long point_add(int l,int r,int a,int b,int k,long add) {
			propagate(k);
			if (r<=a||b<=l) return 0;
			if (a<=l&&r<=b) {
				v[k]+=add;
				return v[k];
			} else {
				long vl=point_add(l,(l+r)/2,a,b,2*k+1,add);
				long vr=point_add((l+r)/2,r,a,b,2*k+2,add);
				v[k]=v[2*k+1]+v[2*k+2];
				return vl+vr;
			}
		}
	}
	
	void run() {
		FastScanner sc = new FastScanner();
		int N=sc.nextInt();
		ArrayList<Integer>[] g=new ArrayList[N];
		for (int i=0;i<N;++i) g[i]=new ArrayList<>();
		for (int i=0;i<N-1;++i) {
			int u=sc.nextInt();
			int v=sc.nextInt();
			g[u].add(v);
			g[v].add(u);
		}
		int[] ord=new int[N];
		int[] par=new int[N];
		int[] dep=new int[N];
		int[] L1=new int[N];
		int[] R1=new int[N];
		int[] L2=new int[N];
		int[] R2=new int[N];
		{
			Arrays.fill(ord, -1);
			Arrays.fill(par, -1);
			ArrayDeque<Integer> dq=new ArrayDeque<>();
			dq.add(0);
			int p=0;
			ord[0]=p++;
			while (!dq.isEmpty()) {
				int cur=dq.pollFirst();
				for (int dst:g[cur]) {
					if (dst==par[cur]) continue;
					dq.addLast(dst);
					ord[dst]=p++;
					par[dst]=cur;
					dep[dst]=dep[cur]+1;
				}
			}
			for (int i=0;i<N;++i) {
				L1[i]=L2[i]=N;
				R1[i]=R2[i]=-1;
			}
			for (int i=0;i<N;++i) {
				if (dep[i]>=1) {
					L1[par[i]]=Math.min(L1[par[i]], ord[i]);
					R1[par[i]]=Math.max(R1[par[i]], ord[i]);
				}
				if (dep[i]>=2) {
					L2[par[par[i]]]=Math.min(L2[par[par[i]]], ord[i]);
					R2[par[par[i]]]=Math.max(R2[par[par[i]]], ord[i]);
				}
			}
		}
		long[] A=new long[N];
		for (int i=0;i<N;++i) A[i]=sc.nextLong();
		Seg seg=new Seg(N);
		for (int i=0;i<N;++i) seg.point_add(i, i+1, A[i]);
		int Q=sc.nextInt();
		PrintWriter pw=new PrintWriter(System.out);
		while (Q-->0) {
			int x=sc.nextInt();
			long add=seg.point_add(L1[x],R1[x]+1,0)+seg.point_add(L2[x],R2[x]+1,0);
			seg.range_clear(L1[x],R1[x]+1);
			seg.range_clear(L2[x],R2[x]+1);
			if (dep[x]>=2) {
				add+=seg.point_add(ord[par[par[x]]],ord[par[par[x]]]+1,0);
				seg.range_clear(ord[par[par[x]]],ord[par[par[x]]]+1);
			}
			if (dep[x]>=1) {
				add+=seg.point_add(ord[par[x]],ord[par[x]]+1,0);
				add+=seg.point_add(L1[par[x]],R1[par[x]]+1,0);
				seg.range_clear(ord[par[x]],ord[par[x]]+1);
				seg.range_clear(L1[par[x]],R1[par[x]]+1);
			}
			seg.point_add(ord[x],ord[x]+1,add);
			pw.println(seg.point_add(ord[x],ord[x]+1,0));
		}
		pw.flush();
	}
	
	void tr(Object...o) {System.out.println(Arrays.deepToString(o));}
}

yukicoder

結果

テストケース

ソースコード