Submission #1111005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111005		LilPluton	Paths (RMI21_paths)	C++14	0 / 100	1044 ms	24648 KiB

Main

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32