Submission #863205

#	Time	Username	Problem	Language	Result	Execution time	Memory
863205		Irate	Janjetina (COCI21_janjetina)	C++14	15 / 110	16 ms	24156 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e3 + 3;
vector<pair<int, int>> G[mxN];
int depth[mxN][mxN], path_mx[mxN][mxN];
void dfs(int node, int par, int root){
    for(pair<int, int> &v : G[node]){
        if(v.first != par){
            depth[root][v.first] = depth[root][node] + 1;
            path_mx[root][v.first] = max(path_mx[root][node], v.second);
            dfs(v.first, node, root);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1;i < n;++i){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for(int i = 1;i <= n;++i){
        dfs(i, i, i);
    }
    long long res = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            if(i != j && path_mx[i][j] - depth[i][j] >= k){
                res++;
            }
        }
    }
    cout << res;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60