oj.uz

Submission #533516

# Submission time Handle Problem Language Result Execution time Memory
533516 2022-03-06T08:29:53 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
10 / 110
 70 ms 14140 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, dp[N];
bool have[N];

void dfs(int v, int pr, int d, int cur)
{
    if (have[v])
    {
        mx = min(mx, cur);

        return;
    }

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

void dfs1(int v, int pr)
{
    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dp[v] = max(dp[v], dp[u] + 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 << ' ';
}

void group2()
{
    dfs1(1, 1);

    ll ans = 1e18;
    int nom;
    for(int i = 1; i <= n; i++)
    {
        ll mx = 0;
        for(auto [u, w] : g[i])
          mx = max(mx, dp[u]);
        if (mx < ans)
        {
            ans = mx;
            nom = i;
        }
    }

    cout << ans << '\n';
    cout << nom;
}

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();
    else if (k == 1) group2();

}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Correct 7 ms 5028 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 29 ms 4940 KB Output is correct
7 Correct 23 ms 4940 KB Output is correct
8 Correct 12 ms 5032 KB Output is correct
9 Correct 60 ms 5016 KB Output is correct
10 Correct 11 ms 4940 KB Output is correct
11 Correct 39 ms 5012 KB Output is correct
12 Correct 70 ms 4940 KB Output is correct
13 Correct 7 ms 4940 KB Output is correct
14 Correct 43 ms 5028 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 14140 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Correct 7 ms 5028 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 29 ms 4940 KB Output is correct
7 Correct 23 ms 4940 KB Output is correct
8 Correct 12 ms 5032 KB Output is correct
9 Correct 60 ms 5016 KB Output is correct
10 Correct 11 ms 4940 KB Output is correct
11 Correct 39 ms 5012 KB Output is correct
12 Correct 70 ms 4940 KB Output is correct
13 Correct 7 ms 4940 KB Output is correct
14 Correct 43 ms 5028 KB Output is correct
15 Incorrect 57 ms 13892 KB Output isn't correct
16 Halted 0 ms 0 KB -