village/Village_artur.java
1 import java.io.BufferedReader;
2 import java.io.InputStreamReader;
3 import java.util.Arrays;
4 import java.util.HashMap;
5 import java.util.Map;
6 import java.util.StringTokenizer;
7
8 public class Village_artur {
9
10 static final int MAXN = 100100;
11
12 static int n, id, k;
13 static int[] a = new int[MAXN * 3], b = new int[MAXN], l = new int[MAXN], r = new int[MAXN];
14 static Map<Integer, Boolean>[] graph = new HashMap[MAXN];
15
16 static {
17 for (int i = 0; i < MAXN; i++)
18 graph[i] = new HashMap<Integer, Boolean>();
19 }
20
21 public static void main(String[] args) throws Exception {
22 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
23
24 while (true) {
25 StringTokenizer str = new StringTokenizer(in.readLine());
26 n = Integer.parseInt(str.nextToken());
27 int m = Integer.parseInt(str.nextToken());
28 int queries = Integer.parseInt(str.nextToken());
29
30 if (n == 0 && m == 0 && queries == 0)
31 break;
32
33 for (int i = 0; i < n; i++) {
34 a[i] = b[i] = -1;
35 graph[i].clear();
36 }
37
38 for (int i = 0; i < m; i++) {
39 str = new StringTokenizer(in.readLine());
40 int p = Integer.parseInt(str.nextToken()) - 1;
41 int q = Integer.parseInt(str.nextToken()) - 1;
42 if (graph[p].containsKey(q))
43 graph[p].put(q, false);
44 else
45 graph[p].put(q, null);
46 if (graph[q].containsKey(p))
47 graph[q].put(p, false);
48 else
49 graph[q].put(p, null);
50 }
51
52 k = 0;
53 find_bridges(0, -1);
54
55 k = 0;
56 id = 0;
57 for (int i = 0; i < n; i++) {
58 a[i] = r[i] = -1;
59 l[i] = n;
60 }
61 color_components(0, id++);
62
63 Arrays.fill(a, 0);
64 for (int query = 0; query < queries; query++) {
65 str = new StringTokenizer(in.readLine());
66 if ("+".equals(str.nextToken())) {
67 id = Integer.parseInt(str.nextToken()) - 1;
68 k = Integer.parseInt(str.nextToken());
69 increment(0, 0, n - 1, l[b[id]], r[b[id]]);
70 } else {
71 id = l[b[Integer.parseInt(str.nextToken()) - 1]];
72 System.out.println(query(0, 0, n - 1));
73 }
74 }
75 }
76 }
77
78 static void color_components(int i, int color) {
79 b[i] = color;
80 a[i] = k++;
81 l[color] = Math.min(l[color], a[i]);
82 r[color] = Math.max(r[color], a[i]);
83 for (int j : graph[i].keySet())
84 if (a[j] == -1)
85 if (graph[i].get(j) != Boolean.TRUE)
86 color_components(j, color);
87 else {
88 int newcolor = id++;
89 color_components(j, newcolor);
90 r[color] = Math.max(r[color], r[newcolor]);
91 }
92 }
93
94 static void find_bridges(int i, int parent) {
95 a[i] = b[i] = ++k;
96 for (int j : graph[i].keySet())
97 if (j != parent)
98 if (a[j] == -1) {
99 find_bridges(j, i);
100 b[i] = Math.min(b[i], b[j]);
101 } else
102 b[i] = Math.min(b[i], a[j]);
103
104 if (parent != -1 && a[i] == b[i] && graph[i].get(parent) == null) {
105 graph[i].put(parent, true);
106 graph[parent].put(i, true);
107 }
108 }
109
110 static int query(int node, int left, int right) {
111 if (left == id && right == id)
112 return a[node];
113
114 int mid = (left + right) / 2;
115 if (id > mid)
116 return query(2 * node + 2, mid + 1, right) + a[node];
117 else
118 return query(2 * node + 1, left, mid) + a[node];
119 }
120
121 static void increment(int node, int left, int right, int begin, int end) {
122 if (left > end || begin > right)
123 return;
124
125 if (left == begin && end == right)
126 a[node] += k;
127 else {
128 int mid = (left + right) / 2;
129 increment(2 * node + 1, left, mid, begin, Math.min(end, mid));
130 increment(2 * node + 2, mid + 1, right, Math.max(begin, mid + 1), end);
131 }
132 }
133 }