Submission #315736

#TimeUsernameProblemLanguageResultExecution timeMemory
315736KWang31Graph (BOI20_graph)Java
34 / 100
709 ms71836 KiB
import java.io.*; import java.util.*; public class Graph { public static class Pair{ int vtx; int val; public Pair(int a, int b){ this.vtx=a; this.val=b; } } public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st=new StringTokenizer(br.readLine()); int N=Integer.parseInt(st.nextToken()); int M=Integer.parseInt(st.nextToken()); ArrayList<Pair> 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++) { st=new StringTokenizer(br.readLine()); a=Integer.parseInt(st.nextToken())-1; b=Integer.parseInt(st.nextToken())-1; vv=Integer.parseInt(st.nextToken()); arl[a].add(new Pair(b,2*vv)); arl[b].add(new Pair(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++; Queue<Integer> qu2=new LinkedList<>();//Tracks all vertices in the queue qu2.add(pt); boolean fix=false; while(!qu.isEmpty()){ int v=qu.poll(); for (Pair p : arl[v]) { if(!vis[p.vtx]){ vis[p.vtx]=true; qu.add(p.vtx); if(!fix){ qu2.add(p.vtx); } m[p.vtx]=-m[v]; c[p.vtx]=p.val-c[v]; done++; }else{ if(m[p.vtx]==m[v] && m[v]!=0){ //m[p.vtx]x+c[p.vtx]+m[v]x+c[v] is known int x=(p.val-c[p.vtx]-c[v])/(2*m[p.vtx]); fix=true; for(int vtx: qu2){ c[vtx]+=m[vtx]*x; m[vtx]=0; } }else if(m[p.vtx]+m[v]==0){//m[v]=0 if(c[p.vtx]+c[v]!=p.val){ 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<>(); Queue<Integer> qu3=new LinkedList<>(); for (int i : qu2) { if(m[i]<0){ m[i]=-m[i]; c[i]=-c[i]; qu3.add(i); } arl2.add(c[i]); } Collections.sort(arl2); int med=arl2.get(arl2.size()/2); for (int i : qu2) { c[i]-=med; } while(!qu3.isEmpty()){ int i=qu3.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...