Submission #1364839
Source Code Expand
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 Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | threepipes_s |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 4160 Byte |
Status | AC |
Exec Time | 911 ms |
Memory | 90684 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 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 | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
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 |