QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326794 | #5580. Branch Manager | trua | WA | 866ms | 120120kb | Java11 | 1.9kb | 2024-02-14 03:39:19 | 2024-02-14 03:39:19 |
Judging History
answer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.*;
import java.util.*;
public class branchmanager {
public static long eulerCount;
public static long[][] eulerTour;
public static ArrayList<Integer> adj[];
public static void main(String[] args) throws IOException{
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(r.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
eulerTour = new long[n][2];
adj = new ArrayList[n];
for (int i=0; i< n; i++) {
adj[i] = new ArrayList<Integer>();
}
for (int i=0; i< n-1; i++) {
st = new StringTokenizer(r.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
adj[a].add(b);
}
for (int i=0; i< adj.length; i++) {
Collections.sort(adj[i]);
}
eulerCount = 0;
dfs(0);
long eulerBorder = 0; // can't pick any nodes less than the eulerBorder (can only pick bigger nodes)
for (int i=0; i< m; i++) {
int node = Integer.parseInt(r.readLine()) - 1;
if (eulerTour[node][1] < eulerBorder) {
pw.println(node);
pw.close();
}
else {
eulerBorder = Math.max(eulerBorder, eulerTour[node][0]);
}
}
pw.println(m);
pw.close();
}
public static void dfs(int node) {
eulerTour[node][0] = eulerCount;
for (int i:adj[node]) {
eulerCount++;
dfs(i);
}
eulerCount++;
eulerTour[node][1] = eulerCount;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 53ms
memory: 49136kb
input:
8 5 1 2 4 8 4 6 1 4 2 5 4 7 2 3 5 2 6 4 8
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 46ms
memory: 48660kb
input:
4 4 1 2 1 3 1 4 3 2 3 4
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 50ms
memory: 49260kb
input:
2 2 1 2 2 2
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 866ms
memory: 120120kb
input:
200000 200000 161672 172858 146306 146322 61159 61510 140802 145171 194221 195447 73888 80278 77016 77115 1382 1417 186221 195091 78442 78451 171750 172141 147707 151432 182664 182798 143183 147414 156646 162546 6630 6706 18452 18519 99764 99811 153419 153707 125659 129068 179317 185954 13947 14278 ...
output:
396
result:
wrong answer 1st lines differ - expected: '3563', found: '396'