AtCoder Grand Contest 012

Submission #1364839

Source codeソースコード

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Main {
	static ContestScanner in;
	static Writer out;
	public static void main(String[] args) {
		Main main = new Main();
		try {
			in = new ContestScanner();
			out = new Writer();
			main.solve();
			out.close();
			in.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	void solve() throws IOException {
		int n = in.nextInt();
		int m = in.nextInt();
		Data[][] frame = new Data[n][11];
		Data[][] frameIn = new Data[n][11];
		List<Integer>[] node = new List[n];
		for(int i = 0; i < n; i++) node[i] = new ArrayList<>();
		for(int i = 0; i < m; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			node[a].add(b);
			node[b].add(a);
		}
		int q = in.nextInt();
		int[] maxT = new int[n];
		Arrays.fill(maxT, -1);
		int[] maxC = new int[n];
		for(int i = 0; i < q; i++) {
			int v = in.nextInt() - 1;
			int d = in.nextInt();
			int c = in.nextInt();
			frameIn[v][d] = new Data(c, i);
		}
		for(int t = 0; t < 10; t++) {
			for(int i = 0; i < n; i++) {
				// move Data from frameIn to frame
				for(int j = 0; j <= 10; j++) {
					if(frameIn[i][j] == null) continue;
					Data d = frameIn[i][j];
					frameIn[i][j] = null;
					if(d.time > maxT[i]) {
						maxT[i] = d.time;
						maxC[i] = d.col;
					}
					if(frame[i][j] == null || frame[i][j].time < d.time) {
						frame[i][j] = d;
					}
				}
				
				// update network
				for(int v: node[i]) {
					for(int j = 1; j <= 10; j++) {
						if(frame[i][j] == null
								|| frameIn[v][j - 1] != null
								&& frameIn[v][j - 1].time >= frame[i][j].time)
							continue;
						frameIn[v][j - 1] = frame[i][j];
					}
				}
			}
		}
		
		for(int i = 0; i < n; i++) {
			out.println(maxC[i]);
		}
	}
}

class Data {
	int col, time;
	Data(int col, int time) {
		this.col = col;
		this.time = time;
	}
}

@SuppressWarnings("serial")
class MultiSet<T> extends HashMap<T, Integer>{
	@Override public Integer get(Object key){return containsKey(key)?super.get(key):0;}
	public void add(T key,int v){put(key,get(key)+v);}
	public void add(T key){put(key,get(key)+1);}
	public void sub(T key){final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
	public MultiSet<T> merge(MultiSet<T> set)
	{MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;}
	for(Entry<T,Integer>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;}
}

class Writer extends PrintWriter{
	public Writer(String filename)throws IOException
	{super(new BufferedWriter(new FileWriter(filename)));}
	public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
	private BufferedReader in;private int c=-2;
	public ContestScanner()throws IOException 
	{in=new BufferedReader(new InputStreamReader(System.in));}
	public ContestScanner(String filename)throws IOException
	{in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
	public String nextToken()throws IOException {
		StringBuilder sb=new StringBuilder();
		while((c=in.read())!=-1&&Character.isWhitespace(c));
		while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
		return sb.toString();
	}
	public String readLine()throws IOException{
		StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
		while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
		return sb.toString();
	}
	public long nextLong()throws IOException,NumberFormatException
	{return Long.parseLong(nextToken());}
	public int nextInt()throws NumberFormatException,IOException
	{return(int)nextLong();}
	public double nextDouble()throws NumberFormatException,IOException 
	{return Double.parseDouble(nextToken());}
	public void close() throws IOException {in.close();}
}

Submission

Task問題 B - Splatter Painting
User nameユーザ名 つっつ
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 700
Source lengthソースコード長 4160 Byte
File nameファイル名
Exec time実行時間 911 ms
Memory usageメモリ使用量 90684 KB

Compiler messageコンパイルメッセージ

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt
Subtask1 200 / 200 00_example_01.txt,00_example_02.txt,10_01.txt,10_02.txt,10_03.txt,10_04.txt,10_05.txt,10_06.txt,10_07.txt,10_08.txt,10_09.txt,10_10.txt,10_11.txt,10_12.txt,10_13.txt,10_14.txt,10_15.txt,10_16.txt,10_17.txt
All 500 / 500 00_example_01.txt,00_example_02.txt,10_01.txt,10_02.txt,10_03.txt,10_04.txt,10_05.txt,10_06.txt,10_07.txt,10_08.txt,10_09.txt,10_10.txt,10_11.txt,10_12.txt,10_13.txt,10_14.txt,10_15.txt,10_16.txt,10_17.txt,20_01.txt,20_02.txt,20_03.txt,20_04.txt,20_05.txt,20_06.txt,20_07.txt,20_08.txt,20_09.txt,20_10.txt,20_11.txt,20_12.txt,20_13.txt,20_14.txt,20_15.txt,20_16.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 73 ms 21588 KB
00_example_02.txt AC 72 ms 21588 KB
10_01.txt AC 110 ms 20180 KB
10_02.txt AC 73 ms 20436 KB
10_03.txt AC 74 ms 19668 KB
10_04.txt AC 73 ms 18132 KB
10_05.txt AC 99 ms 20308 KB
10_06.txt AC 76 ms 20948 KB
10_07.txt AC 100 ms 19668 KB
10_08.txt AC 143 ms 25056 KB
10_09.txt AC 143 ms 25244 KB
10_10.txt AC 140 ms 25768 KB
10_11.txt AC 141 ms 24096 KB
10_12.txt AC 147 ms 25108 KB
10_13.txt AC 136 ms 24864 KB
10_14.txt AC 129 ms 25320 KB
10_15.txt AC 123 ms 23576 KB
10_16.txt AC 137 ms 26188 KB
10_17.txt AC 143 ms 24924 KB
20_01.txt AC 881 ms 88680 KB
20_02.txt AC 911 ms 88984 KB
20_03.txt AC 852 ms 90684 KB
20_04.txt AC 306 ms 42488 KB
20_05.txt AC 131 ms 25544 KB
20_06.txt AC 344 ms 58368 KB
20_07.txt AC 139 ms 22836 KB
20_08.txt AC 251 ms 39452 KB
20_09.txt AC 135 ms 24088 KB
20_10.txt AC 197 ms 41656 KB
20_11.txt AC 235 ms 41932 KB
20_12.txt AC 629 ms 81696 KB
20_13.txt AC 766 ms 81972 KB
20_14.txt AC 838 ms 88328 KB
20_15.txt AC 670 ms 87140 KB
20_16.txt AC 699 ms 90548 KB