oj.uz

답안 #533513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533513 2022-03-06T08:24:35 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
10 / 110
 73 ms 14116 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define int long long

const int N = (int)2e5 + 500;
vector< pair<int, int> > g[N];
int n, k, mx, mn_d;
bool have[N];

void dfs(int v, int pr, int d, int cur)
{
    if (have[v])
    {
//        if (d < mn_d)
//        {
//            mx = cur;
//            mn_d = d;
//        }
//        else if (d == mn_d) mx = min(mx, cur);


        mx = min(mx, cur);

        return;
    }

    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dfs(u, v, d + 1, cur + w);
    }
}

void group1()
{
    vector<int> vec;
    int ans = 1e18;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        if (__builtin_popcount(mask) != k) continue;

        for(int i = 1; i <= n; i++) have[i] = 0;
        for(int i = 0; i < n; i++)
          if (mask & (1 << i))
            {
                have[i + 1] = 1;
            }


        int cur_ans = 0;
        for(int i = 1; i <= n; i++)
        {
            mx = 1e18; mn_d = 1e18;
            dfs(i, i, 0, 0);
            cur_ans = max(cur_ans, mx);
        }

        if (ans > cur_ans)
        {
            ans = cur_ans;
            vec.clear();
            for(int i = 0; i < n; i++)
              if (mask & (1 << i))
                vec.pb(i + 1);
        }
    }

    cout << ans << '\n';
    for(auto u : vec) cout << u << ' ';
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> n >> k;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    if (n <= 25) group1();

}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
Main.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [u, w] : g[v])
      |              ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 7 ms 5020 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 5128 KB Output is correct
6 Correct 30 ms 5020 KB Output is correct
7 Correct 22 ms 5024 KB Output is correct
8 Correct 13 ms 4940 KB Output is correct
9 Correct 64 ms 5008 KB Output is correct
10 Correct 12 ms 4940 KB Output is correct
11 Correct 40 ms 4940 KB Output is correct
12 Correct 70 ms 4912 KB Output is correct
13 Correct 9 ms 4940 KB Output is correct
14 Correct 45 ms 4940 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 13776 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 14116 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 7 ms 5020 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 5128 KB Output is correct
6 Correct 30 ms 5020 KB Output is correct
7 Correct 22 ms 5024 KB Output is correct
8 Correct 13 ms 4940 KB Output is correct
9 Correct 64 ms 5008 KB Output is correct
10 Correct 12 ms 4940 KB Output is correct
11 Correct 40 ms 4940 KB Output is correct
12 Correct 70 ms 4912 KB Output is correct
13 Correct 9 ms 4940 KB Output is correct
14 Correct 45 ms 4940 KB Output is correct
15 Incorrect 55 ms 13776 KB Unexpected end of file - int64 expected
16 Halted 0 ms 0 KB -