village/village_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to It Takes a Village
  8  * 
  9  * @author vanb
 10  */
 11 public class village_vanb
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     public static final int MAX = 100000;
 17         
 18     public int tree[] = new int[MAX];
 19     public int treeindex;
 20     
 21     public class Village
 22     {
 23         public Village collapsedto = null;
 24         public Village parent = null;
 25         public LinkedList<Village> roads = new LinkedList<Village>();
 26         public int treenode = -1;
 27         public int index;
 28         public boolean onpath = false, visited = false;
 29         
 30         public void clear()
 31         {
 32             collapsedto = parent = null;
 33             treenode = -1;
 34             roads.clear();
 35             onpath = visited = false;
 36         }
 37         
 38         void collapse( int index, Village from )
 39         {
 40             if( visited )
 41             {
 42                 Village top = this;
 43                 while( !top.onpath ) top = top.parent;
 44                 
 45                 Village village = this;
 46                 while( village!=top )
 47                 {
 48                     village.collapsedto = top;
 49                     village = village.parent;
 50                 }
 51                 
 52                 village = from;
 53                 while( village!=top )
 54                 {
 55                     village.collapsedto = top;
 56                     village = village.parent;
 57                 }
 58                 
 59             }
 60             else
 61             {
 62                 onpath = visited = true;
 63                 parent = from;
 64                 for( Village neighbor : roads ) if( neighbor!=from )
 65                 {
 66                     neighbor.collapse( index, this );
 67                 }
 68                 onpath = false;
 69             }
 70         }
 71         
 72         void buildTree( Village from )
 73         {
 74             if( treenode<0 )
 75             {
 76                 if( collapsedto==null )
 77                 {
 78                     treenode = treeindex++;
 79                 }
 80                 else
 81                 {
 82                     Village v;
 83                     for( v=collapsedto; v.collapsedto!=null; v=v.collapsedto );
 84                     treenode = v.treenode; 
 85                 }
 86                 
 87                 for( Village neighbor : roads ) if( neighbor!=from )
 88                 {
 89                     neighbor.buildTree(this);
 90                 }
 91                 
 92                 tree[treenode] = treeindex-1;
 93             }
 94         }
 95         
 96         public String toString()
 97         {
 98             return "{" + index + ", tree=" + treenode + ", coll=" + (collapsedto==null?-1:collapsedto.index) + "}"; 
 99         }
100         
101     }
102     
103     public Village villages[] = new Village[MAX];
104     
105     public int segtree[] = new int[MAX+MAX+MAX];
106     
107     public void addValue( int x, int start, int end, int index, int istart, int iend )
108     {
109         //System.out.println(  Add   + x +     + start +     + end +     + index +     + istart +     + iend );
110         if( istart<=end && start<=iend )
111         {
112             if( start<=istart && iend<=end) 
113             {
114                 segtree[index] += x;
115             }
116             else
117             {
118                 int mid = (istart+iend)/2;
119                 if( istart<=end && start<=mid )
120                 {
121                     addValue( x, start, end, index*2, istart, mid );
122                 }
123                 if( mid+1<=end && start<=iend )
124                 {
125                     addValue( x, start, end, index*2+1, mid+1, iend );
126                 }
127             }
128         }
129     }
130    
131 //    public int getValue( int start, int end, int index, int istart, int iend )
132 //    {
133 //        int value = segtree[index];
134 //        //System.out.println(  Get   + start +     + end +     + index +     + istart +     + iend );
135 //        
136 //        if( iend>istart )
137 //        {
138 //            int mid = (istart+iend)/2;
139 //            if( istart<=end && start<=mid )
140 //            {
141 //                value += getValue( start, end, index*2, istart, mid );
142 //            }
143 //            if( mid+1<=end && start<=iend )
144 //            {
145 //                value += getValue( start, end, index*2+1, mid+1, iend );
146 //            }
147 //        }
148 //        
149 //        return value;
150 //    }
151     public int getValue( int start, int index, int istart, int iend )
152     {
153         
154         int value = 0;
155 
156         //System.out.println(  Get   + start +     + end +     + index +     + istart +     + iend );
157         
158         while( iend>istart )
159         {
160             value += segtree[index];
161             int mid = (istart+iend)/2;
162             if( start<=mid )
163             {
164                 index = index*2;
165                 iend = mid;
166             }
167             else
168             {
169                 index = index*2+1;
170                 istart = mid+1;
171             }
172         }
173         
174         return value+segtree[index];
175     }
176         
177     /**
178      * Driver.
179      * @throws Exception
180      */
181     public void doit() throws Exception
182     {
183         sc = new Scanner( new File( "village.sample" ) );
184         ps = System.out; //new PrintStream( new FileOutputStream(  village.vanb  ) );
185 
186         for( int i=0; i<MAX; i++ )
187         {
188             villages[i] = new Village();
189             villages[i].index = i;
190         }
191         
192         int c=0;
193         for(;;)
194         {
195             ++c;
196             int n = sc.nextInt();
197             int m = sc.nextInt();
198             int q = sc.nextInt();
199             if( n==0 && m==0 && q==0 ) break;
200         
201             for( int i=0; i<n; i++ )
202             {
203                 villages[i].clear();       
204             }
205             for( int i=0; i<m; i++ )
206             {
207                 Village a = villages[sc.nextInt()-1];
208                 Village b = villages[sc.nextInt()-1];
209                 a.roads.add( b );
210                 b.roads.add( a );
211             }
212             
213             villages[0].collapse( 0, null );
214             Arrays.fill( tree, -1 );
215             treeindex = 0;
216             villages[0].buildTree( null );
217             Arrays.fill( segtree, 0 );
218             
219             for( int i=0; i<q; i++ )
220             {
221                 String command = sc.next();
222                 if( command.equals( "+" ))
223                 {
224                     int k = sc.nextInt()-1;
225                     //if( k<0 || k>=n ) System.err.println(  PANIC!! Bad k! case   + c );
226                     int x = sc.nextInt();
227                     //if( x<1 || x>1000 ) System.err.println(  PANIC!! Bad x! case   + c );
228                     int start = villages[k].treenode;
229                     int end = tree[start];
230                     addValue( x, start, end, 1, 0, n-1 );
231                 }
232                 else if( command.equals( "?" ))
233                 {
234                     int k = sc.nextInt()-1;
235                     //if( k<0 || k>=n ) System.err.println(  PANIC!! Bad k! case   + c );
236                     int start = villages[k].treenode;
237                     ps.println( getValue( start, 1, 0, n-1 ) );
238                 }
239                 else
240                 {
241                     System.err.println( "PANIC!! Unknown command: " + command );
242                 }
243             }
244             
245         }
246     }
247     
248     /**
249      * @param args
250      */
251     public static void main( String[] args ) throws Exception
252     {
253         long start = System.currentTimeMillis();
254         new village_vanb().doit();        
255         System.out.println( System.currentTimeMillis() - start);
256     }   
257 }