QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326794#5580. Branch ManagertruaWA 866ms120120kbJava111.9kb2024-02-14 03:39:192024-02-14 03:39:19

Judging History

你现在查看的是最新测评结果

  • [2024-02-14 03:39:19]
  • 评测
  • 测评结果:WA
  • 用时:866ms
  • 内存:120120kb
  • [2024-02-14 03:39:19]
  • 提交

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'