fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class F
  9. {
  10.  
  11.     int[] P;
  12. 	int[][] D;
  13. 	ArrayList<Integer>[] adj;
  14. 	boolean[] Used;
  15.  
  16. 	public static void main(String[] args)throws java.lang.Exception{
  17. 	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  18. 		PrintWriter out = new PrintWriter(System.out,true);
  19. 		StringTokenizer st = new StringTokenizer(br.readLine());
  20. 		int n = Integer.parseInt(st.nextToken());
  21. 		int m = Integer.parseInt(st.nextToken());
  22. 		int z = Integer.parseInt(st.nextToken());
  23. 		F f = new F();
  24. 		f.P = new int[n+1];
  25. 		f.Used = new boolean[n+1];
  26. 		st = new StringTokenizer(br.readLine());
  27. 		for(int i =1;i<=n;i++)f.P[i] = Integer.parseInt(st.nextToken());
  28. 		f.D = new int[n+1][2];
  29. 		f.adj = new ArrayList[n+1];
  30. 		for(int i =0;i<=n;i++)f.adj[i] = new ArrayList<Integer>();
  31. 		for(int i =0;i<m;i++){
  32. 		    st = new StringTokenizer(br.readLine());
  33. 		    int x = Integer.parseInt(st.nextToken());
  34. 		    int y = Integer.parseInt(st.nextToken());
  35. 		    f.adj[x].add(y);
  36. 		    f.adj[y].add(x);
  37. 		    f.D[i+1][0] = x;
  38. 		    f.D[i+1][1] = y;
  39. 		}
  40. 	//	out.println(f.adj[1].size()+" "+f.adj[2].size()+" "f.adj[3].size());
  41. 		while(z-->0){
  42. 		    long ans = 0,l = 0;
  43. 		    Arrays.fill(f.Used,false);
  44. 		    st = new StringTokenizer(br.readLine());
  45. 		    String s = st.nextToken();
  46. 		    if(s.equals("P")){
  47. 		        int x = Integer.parseInt(st.nextToken());
  48. 		        int y = Integer.parseInt(st.nextToken());
  49. 		        f.P[x] = y;
  50. 		    }
  51. 		    else{
  52. 		        int p = Integer.parseInt(st.nextToken());
  53. 		        int x = f.D[p][0];
  54. 		        int y = f.D[p][1];
  55. 		        int g = f.adj[x].indexOf(y);
  56. 		        int h = f.adj[y].indexOf(x);
  57. 		        //out.println(g+" "+h);
  58. 		        if(g!=-1)
  59. 		        f.adj[x].remove(g);
  60. 		        if(h!=-1)
  61. 		        f.adj[y].remove(h);
  62. 		    }
  63. 		    for(int i = 1;i<=n;i++){
  64. 		        if(!f.Used[i]){
  65. 		            Queue<Integer> q = new LinkedList<Integer>();
  66. 		            l = 0;
  67. 		            q.add(i);
  68. 		            f.Used[i] = true;
  69. 		            while(q.size()!=0){
  70. 		                int t = q.remove();
  71. 		                l += f.P[t];
  72. 		               // out.println(f.P[t] + " "+t);
  73. 		                for(int k:f.adj[t]){
  74. 		                    if(!f.Used[k]){
  75. 		                        q.add(k);
  76. 		                        f.Used[k] = true;
  77. 		                    }
  78. 		                }
  79. 		            }
  80. 		        }
  81. 		        if(l>ans)ans = l;
  82. 		    }
  83. 		    out.println(ans);
  84. 		}
  85. 	}
  86. }
Success #stdin #stdout 0.1s 320576KB
comments (?)
stdin
copy 
3 3 6
1 2 3
1 2
2 3
3 1
P 1 3
D 1
P 2 3
D 2
P 3 10
D 3
stdout
copy 
8
8
9
6
13
10
https://ideone.com/lKYrAm
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!