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ユーザ名 018_threepipes_s
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