oj.uz

Submission #702779

# Submission time Handle Problem Language Result Execution time Memory
702779 2023-02-25T06:52:17 Z Nursik Paths (RMI21_paths) C++14
8 / 100
 45 ms 488 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 #include <cstdint>
#include <cassert>
#include <functional>
#include <complex>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 1e3 + 10, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int n, k;
int x[maxn], y[maxn], c[maxn], used[maxn];
int par[maxn], reb[maxn];
vector<pair<int, int>> g[maxn];
void dfs(int v, int p){
    for (auto to : g[v]){
        if (to.f != p){
            par[to.f] = v;
            reb[to.f] = to.s;
            dfs(to.f, v);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; ++i){
        cin >> x[i] >> y[i] >> c[i];
        g[x[i]].pb(mp(y[i], i));
        g[y[i]].pb(mp(x[i], i));
    }
    for (int i = 1; i <= n; ++i){
        par[i] = 0;
        dfs(i, 0);
        ll ans = 0;
        for (int j = 0; j < (1 << n); ++j){
            int z = __builtin_popcount(j);
            ll cur = 0;
            if (z == k){
                for (int jj = 0; jj < n; ++jj){
                    if ((1 << jj) & j){
                        int v = jj + 1;
                        while (par[v] > 0){
                            int zz = reb[v];
                            if (used[zz] == 0){
                                cur += c[zz];
                                used[zz] = 1;
                            }
                            v = par[v];
                        }
                    }
                }
                ans = max(ans, cur);
                for (int jj = 1; jj < n; ++jj){
                    used[jj] = 0;
                }
            }
        }
        cout << ans << " ";
    }
}
/*
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 340 KB Output is correct
2 Correct 18 ms 372 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 340 KB Output is correct
2 Correct 18 ms 372 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 340 KB Output is correct
2 Correct 18 ms 372 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 340 KB Output is correct
2 Correct 18 ms 372 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 340 KB Output is correct
2 Correct 18 ms 372 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -