oj.uz

Submission #412071

# Submission time Handle Problem Language Result Execution time Memory
412071 2021-05-26T13:18:47 Z 최서현(#7464) Pastiri (COI20_pastiri) C++17
8 / 100
 361 ms 34644 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

vector<int> gph[505050];
bool chc[505050];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    for(int i = 1; i < n; ++i)
    {
        int x, y; cin >> x >> y; --x; --y;
        gph[x].push_back(y);
        gph[y].push_back(x);
    }
    for(int i = 0; i < k; ++i)
    {
        int x; cin >> x; --x;
        chc[x] = true;
    }

    vector<int> V;
    int dp[k + 1]{};
    pii dir[k + 1]{};
    for(int i = 0; i < n; ++i) if(chc[i]) V.push_back(i);
    for(int i = 0; i < k; ++i)
    {
        if(i > 0 && (V[i] - V[i - 1]) % 2 == 0) dp[i + 1] = 1 + dp[i - 1], dir[i + 1] = {(V[i] + V[i - 1]) / 2, 2};
        else dp[i + 1] = 1 + dp[i], dir[i + 1] = {V[i], 1};
    }
    cout << dp[k] << '\n';
    int pt = k;
    while(pt) cout << dir[pt].ff + 1 << ' ', pt -= dir[pt].ss;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 27772 KB Output is correct
2 Correct 160 ms 28312 KB Output is correct
3 Correct 158 ms 28216 KB Output is correct
4 Correct 235 ms 34644 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12304 KB Sheep 3030 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12236 KB Sheep 86 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 361 ms 28680 KB Sheep 54 not protected
2 Halted 0 ms 0 KB -