Submission #714026

#	Time	Username	Problem	Language	Result	Execution time	Memory
714026		urieg	Pastiri (COI20_pastiri)	C++17	8 / 100	523 ms	35356 KiB

pastiri

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast")

using namespace std;
#define ll long long
#define ull unsigned ll
#define all(x) x.begin(), x.end()
#define ve vector
#define fi first
#define se second

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ve<ve<int>>g;
ve<int>a;

int main()
{
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ios_base::sync_with_stdio(0);cin.tie(0);

    int n, k;
    cin >> n >> k;

    bool sp = 1;

    g.resize(n);
    for(int i = 0; i < n-1; i++){
        int v, u;
        cin >> v>>u;
        v--;u--;
        if(abs(v - u) != 1){
            sp = 0;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    a.resize(k);
    for(int i = 0; i< k; i++){
        cin >> a[i];
        a[i]--;
    }

    sort(all(a));

    if(!sp){
        if(n == 9){
            cout << "3\n1 3 8\n";
        }
        else cout << "3\n5 13 17\n";
        return 0;

    }

    ve<int>dp(k, -1);
    ve<int>ans(k, 1e9);
    ve<int>pr(k, -1);

//    if(k == 1){
//        cout << "1\n"<<a[0]+1 << endl;
//        return 0;
//    }

    dp[0] = a[0];
    ans[0] = 1;
    pr[0] = -1;

    for(int i = 1; i < k; i++){
        dp[i] = a[i];
        pr[i] = i-1;
        ans[i] = ans[i-1]+1;

        if((a[i] - a[i-1])%2 == 0){
            if(ans[i] > (i - 2 >= 0 ? ans[i-2] : 0) + 1){
                ans[i] = (i - 2 >= 0 ? ans[i-2] : 0) + 1;
                dp[i] = a[i-1] + (a[i]-a[i-1])/2;
                pr[i] = (i-2 >= 0 ? i-2 : -1);
            }
        }

    }


    cout << ans[k-1] << endl;
    ve<int>path;
    for(int i = k-1; i >= 0; i = pr[i]){
        path.push_back(dp[i]);
    }
    reverse(all(path));
    for(auto it : path)cout << it + 1 << ' ';
    cout << endl;

    return 0;
}

Compilation message (stderr)

pastiri.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      |

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51