oj.uz

Submission #533518

# Submission time Handle Problem Language Result Execution time Memory
533518 2022-03-06T08:33:36 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
10 / 110
 109 ms 31312 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] = dp1[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 7 ms 4940 KB Output is correct
3 Correct 6 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 32 ms 4940 KB Output is correct
7 Correct 24 ms 5024 KB Output is correct
8 Correct 12 ms 5028 KB Output is correct
9 Correct 66 ms 5004 KB Output is correct
10 Correct 13 ms 4940 KB Output is correct
11 Correct 41 ms 4940 KB Output is correct
12 Correct 73 ms 5004 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 47 ms 5020 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 14148 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 7 ms 4940 KB Output is correct
3 Correct 6 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 32 ms 4940 KB Output is correct
7 Correct 24 ms 5024 KB Output is correct
8 Correct 12 ms 5028 KB Output is correct
9 Correct 66 ms 5004 KB Output is correct
10 Correct 13 ms 4940 KB Output is correct
11 Correct 41 ms 4940 KB Output is correct
12 Correct 73 ms 5004 KB Output is correct
13 Correct 8 ms 4940 KB Output is correct
14 Correct 47 ms 5020 KB Output is correct
15 Incorrect 109 ms 31312 KB Output isn't correct
16 Halted 0 ms 0 KB -