oj.uz

Submission #533517

# Submission time Handle Problem Language Result Execution time Memory
533517 2022-03-06T08:30:54 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
10 / 110
 79 ms 29844 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;
        dfs1(u, v);
        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:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for(auto [u, w] : g[i])
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 6 ms 4968 KB Output is correct
3 Correct 8 ms 4940 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 7 ms 4940 KB Output is correct
6 Correct 32 ms 5016 KB Output is correct
7 Correct 23 ms 4940 KB Output is correct
8 Correct 15 ms 5032 KB Output is correct
9 Correct 65 ms 4940 KB Output is correct
10 Correct 13 ms 4940 KB Output is correct
11 Correct 51 ms 4940 KB Output is correct
12 Correct 78 ms 5008 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 43 ms 5016 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 14180 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 6 ms 4940 KB Output is correct
2 Correct 6 ms 4968 KB Output is correct
3 Correct 8 ms 4940 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 7 ms 4940 KB Output is correct
6 Correct 32 ms 5016 KB Output is correct
7 Correct 23 ms 4940 KB Output is correct
8 Correct 15 ms 5032 KB Output is correct
9 Correct 65 ms 4940 KB Output is correct
10 Correct 13 ms 4940 KB Output is correct
11 Correct 51 ms 4940 KB Output is correct
12 Correct 78 ms 5008 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 43 ms 5016 KB Output is correct
15 Incorrect 79 ms 29844 KB Output isn't correct
16 Halted 0 ms 0 KB -