Submission #332602

#TimeUsernameProblemLanguageResultExecution timeMemory
332602KWang31Graph (BOI20_graph)Java
34 / 100
790 ms21348 KiB
import java.io.*; import java.util.*; public class Graph { static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } public static void main(String[] args) throws IOException { FastReader br=new FastReader(); int N=br.nextInt(); int M=br.nextInt(); ArrayList<Integer> arl[]=new ArrayList[N]; for (int i = 0; i < N; i++) { arl[i]=new ArrayList<>(); } int a,b,vv; for (int i = 0; i < M; i++) { a=br.nextInt()-1; b=br.nextInt()-1; vv=br.nextInt(); arl[a].add(4*b+2*vv); arl[b].add(4*a+2*vv); } boolean[] vis=new boolean[N]; int[] m=new int[N]; int[] c=new int[N]; int done=0; int pt=0; while(done<N){ while(pt<N && vis[pt]){ pt++; } //Start DFS at pt, finish the component m[pt]=1; //b[pt]=0 Queue<Integer> qu=new LinkedList<>(); qu.add(pt); vis[pt]=true; done++; ArrayList<Integer> qu2=new ArrayList<>();//Tracks all vertices in the queue qu2.add(pt); boolean fix=false; int x,y; while(!qu.isEmpty()){ int v=qu.poll(); for (int p : arl[v]) { x=4-p%4; y=(p-x)/4; if(!vis[y]){ vis[y]=true; qu.add(y); if(!fix){ qu2.add(y); } m[y]=-m[v]; c[y]=x-c[v]; done++; }else{ //System.out.println(x+" "+y+" "+v); if(m[y]==m[v] && m[v]!=0){ //m[p.vtx]x+c[p.vtx]+m[v]x+c[v] is known int xx=(x-c[y]-c[v])/(2*m[y]); fix=true; for(int vtx: qu2){ c[vtx]+=m[vtx]*xx; m[vtx]=0; } }else if(m[y]+m[v]==0){//m[v]=0 if(c[y]+c[v]!=x){ System.out.println("NO"); return; } } } } //System.out.println(Arrays.toString(m)); //System.out.println(Arrays.toString(c)); } if(m[pt]!=0){//This component is not fixed ArrayList<Integer> arl2=new ArrayList<>(); for (int i : qu2) { if(m[i]<0){ m[i]=-m[i]; c[i]=-c[i]; qu.add(i); } arl2.add(c[i]); } Collections.sort(arl2); int med=arl2.get(arl2.size()/2); for (int i : qu2) { c[i]-=med; } while(!qu.isEmpty()){ int i=qu.poll(); c[i]=-c[i]; } } } System.out.println("YES"); StringBuilder sb=new StringBuilder(); for (int i = 0; i < N; i++) { sb.append((double)c[i]/2).append(" "); } System.out.println(sb.toString()); } }

Compilation message (stderr)

Note: Graph.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...