/ SeriousOJ /

Record Detail

Wrong Answer


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

Code

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> values;
vector<bool> visited;
int N, K;

void printPath(const vector<int>& path) {
    cout << "Path: ";
    for(int node : path) {
        cout << node << " ";
    }
    int weight = 0;
    for(int node : path) {
        weight += values[node-1];
    }
    cout << "Weight: " << weight << endl;
}

int findMaxPathWeight(int node, int pathLength, vector<int>& currentPath) {
    // Base case: if we have a path of length K
    if (pathLength == K) {
        printPath(currentPath);
        int totalWeight = 0;
        for(int n : currentPath) {
            totalWeight += values[n-1];
        }
        return totalWeight;
    }
    
    visited[node] = true;
    int maxWeight = 0;
    
    // Try each neighbor
    for(int next : adj[node]) {
        if(!visited[next]) {
            currentPath.push_back(next);
            int weight = findMaxPathWeight(next, pathLength + 1, currentPath);
            maxWeight = max(maxWeight, weight);
            currentPath.pop_back();
        }
    }
    
    visited[node] = false;
    return maxWeight;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> K;
    
    adj.resize(N + 1);
    values.resize(N);
    visited.resize(N + 1, false);
    
    cout << "Reading " << N << " values:" << endl;
    for(int i = 0; i < N; i++) {
        cin >> values[i];
        cout << "Value[" << (i+1) << "] = " << values[i] << endl;
    }
    
    cout << "Reading " << (N-1) << " edges:" << endl;
    for(int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        cout << "Edge: " << u << " - " << v << endl;
    }
    
    vector<int> currentPath = {1};
    int result = findMaxPathWeight(1, 1, currentPath);
    
    cout << "Final result: " << result << endl;
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1160 Max path sum (Easy Version)
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-18 10:10:04
Judged At
2025-01-18 10:10:04
Judged By
Score
0
Total Time
1ms
Peak Memory
540.0 KiB