oj.uz

Submission #533525

# Submission time Handle Problem Language Result Execution time Memory
533525 2022-03-06T08:54:43 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
10 / 110
 85 ms 31332 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], dp1[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, int cst)
{
    dp1[v] = max(dp1[pr], dp[pr]) + cst;
    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dfs1(u, v, w);
        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, 0);

    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], dp1[i]});
        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, long long int)':
Main.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [u, w] : g[v])
      |              ^
Main.cpp: In function 'void group2()':
Main.cpp:100:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |         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 9 ms 5024 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 32 ms 5000 KB Output is correct
7 Correct 24 ms 5024 KB Output is correct
8 Correct 12 ms 4940 KB Output is correct
9 Correct 64 ms 4940 KB Output is correct
10 Correct 20 ms 5020 KB Output is correct
11 Correct 44 ms 4940 KB Output is correct
12 Correct 72 ms 5004 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 45 ms 5000 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 14096 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 9 ms 5024 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 32 ms 5000 KB Output is correct
7 Correct 24 ms 5024 KB Output is correct
8 Correct 12 ms 4940 KB Output is correct
9 Correct 64 ms 4940 KB Output is correct
10 Correct 20 ms 5020 KB Output is correct
11 Correct 44 ms 4940 KB Output is correct
12 Correct 72 ms 5004 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 45 ms 5000 KB Output is correct
15 Incorrect 85 ms 31332 KB Output isn't correct
16 Halted 0 ms 0 KB -