This repository was archived by the owner on Feb 29, 2024. It is now read-only.
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmilkvisits.java
More file actions
Latest commit
98 lines (93 loc) · 2.57 KB
/
Copy pathmilkvisits.java
File metadata and controls
98 lines (93 loc) · 2.57 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
importjava.io.*;
importjava.util.*;
publicclassmilkvisits {
publicstaticvoidmain(String[] args) throwsIOException {
BufferedReaderf = newBufferedReader(newFileReader("milkvisits.in"));
PrintWriterpw = newPrintWriter(newBufferedWriter(newFileWriter("milkvisits.out")));
StringTokenizerst = newStringTokenizer(f.readLine());
intN = Integer.parseInt(st.nextToken());
intM = Integer.parseInt(st.nextToken());
char[] lookup = f.readLine().toCharArray();
Map<Integer, List<Integer>> connections = newHashMap<>();
for(inti =1 ; i < (N+1); i ++) {
connections.put(i, newArrayList<>());
}
for(inti = 0; i < N-1; i ++) {
st = newStringTokenizer(f.readLine());
intx = Integer.parseInt(st.nextToken());
inty = Integer.parseInt(st.nextToken());
connections.get(x).add(y);
connections.get(y).add(x);
}
int[] seg = newint[N];
intsegNum = 1;
Stack<Traversal> ts = newStack<>();
//int test = 0;
//char target = lookup[test];
for(inti = 1; i < (N+1); i ++) {
segNum++;
if(seg[i-1] != 0) {
continue;
}
chartarget = lookup[i-1];
ts.push(newTraversal(i));
while(!ts.empty()) {
Traversalt = ts.pop();
seg[t.lastNode-1] = segNum;
for(intnode: connections.get(t.lastNode)) {
if(lookup[node-1] == target && seg[node-1]==0) {
ts.push(newTraversal(node));
}
}
}
}
//System.out.println("Node numbers : {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...}");
//System.out.println("Generated Seg Data: "+Arrays.toString(seg));
//System.out.println("Lookup database : "+Arrays.toString(lookup));
for(inti = 0; i < M; i ++) {
st = newStringTokenizer(f.readLine());
inta = Integer.parseInt(st.nextToken());
intb = Integer.parseInt(st.nextToken());
charT = st.nextToken().charAt(0);
if(seg[a-1] != seg[b-1]) {
pw.print("1");
}else {
if(lookup[a-1] == T && lookup[b-1] == T) {
pw.print("1");
}else {
pw.print("0");
}
}
}
pw.println();
f.close();
pw.close();
}
}
classTraversal {
intlastNode;
publicTraversal(intlastNode) {
this.lastNode = lastNode;
}
}
classPath{
publicintx,y,w;
publicPath(intx,inty) {
this.x = x;
this.y = y;
//this.w = length;
}
@Override
publicbooleanequals(Objecto) {
if(oinstanceofPath) {
Pathp = (Path) o;
return (this.x == p.x)&&(this.y == p.y);
}else {
returnfalse;
}
}
@Override
publicinthashCode() {
returnInteger.hashCode(this.x) * Integer.hashCode(this.y+1);
}
}