oj.uz

Submission #1111005

# Submission time Handle Problem Language Result Execution time Memory
1111005 2024-11-11T09:46:51 Z LilPluton Paths (RMI21_paths) C++14
0 / 100
 600 ms 24648 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define fi first
#define se second
#define vvi vector<vector<int>>
#define ld long double
#define ar array
#define pb push_back
#define vi vector<int>
#define vc vector
#define vpi vector<pair<int,int>>
#define pii pair<int,int>
#define all(c) (c).begin(), (c).end()
#define endll   '\n'
#define fastio  ios::sync_with_stdio(0);cin.tie(0);
#define lb(a, x)    lower_bound(all(a), x) - a.begin();
#define ub(a, x)    upper_bound(all(a), x) - a.begin();
template<typename T> bool umax(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool umin(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
mt19937 rng(time(0));
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
vector<vector<array<int,2>>>adj(N);
map<pair<int,int>,int>mp;
int res = 0, sum = 0;

void dfs(int node,int par){
    if(par != node){
        sum += mp[{node, par}];
    }

    for(auto i:adj[node]){
        if(i[0] == par){
            continue;
        }
        dfs(i[0], node);
    }
    umax(res, sum);
    if(par != node){
        sum -= mp[{node, par}];
    }
    
}

int solve(int root){
    res = 0, sum = 0;
    dfs(root, root);
    return res;
}


signed main() {
    int n, k;
    cin >> n >> k;
    if(k == 1){
        for(int i = 0; i < n - 1; ++i){
            int a, b, c;
            cin >> a >> b >> c;
            adj[a].pb({b, c});
            adj[b].pb({a, c});
            mp[{a, b}] += c;
            mp[{b, a}] += c;
        }
        for(int i = 1; i <= n; ++i){
            cout << solve(i) << endl;
        }
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 24648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -