/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 1ms 540.0 KiB
#2 Wrong Answer 2ms 496.0 KiB

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void solve() {
    int T;
    cin >> T;

    while (T--) {
        int N, Q;
        cin >> N >> Q;

        vector<vector<int>> tree(N + 1);
        for (int i = 0; i < N - 1; ++i) {
            int U, V;
            cin >> U >> V;
            tree[U].push_back(V);
            tree[V].push_back(U);
        }

        // BFS to calculate levels
        vector<int> level(N + 1, -1);
        queue<int> q;
        q.push(1);
        level[1] = 0;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : tree[node]) {
                if (level[neighbor] == -1) {
                    level[neighbor] = level[node] + 1;
                    q.push(neighbor);
                }
            }
        }

        // Frequency and prefix sum calculation
        vector<int> freq(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            freq[level[i]]++;
        }

        vector<int> prefixSum(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            prefixSum[i] = prefixSum[i - 1] + freq[i];
        }

        // Answering queries
        while (Q--) {
            int X;
            cin >> X;
            cout << (X < N ? prefixSum[X] : N) << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-07 14:18:11
Judged At
2024-12-07 14:18:11
Judged By
Score
0
Total Time
2ms
Peak Memory
540.0 KiB