oj.uz

Submission #557706

# Submission time Handle Problem Language Result Execution time Memory
557706 2022-05-06T00:06:39 Z Yazan_Alattar Pastiri (COI20_pastiri) C++14
18 / 100
 1000 ms 104356 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 500007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

queue <int> q;
vector <int> ans, adj[M];
pair <int,int> from[M];
int n, k, a[M], dep[M], anc[M][21], dp[M], nearer[M], pos[M];

void dfs(int node, int p){
    for(auto i : adj[node]) if(i != p){
        dep[i] = dep[node] + 1;
        anc[i][0] = node;
        dfs(i, node);
    }
    return;
}

int lca(int x, int y){
    if(x == y) return x;
    if(dep[x] > dep[y]) swap(x, y);

    for(int j = 19; j >= 0; --j) if(dep[anc[y][j]] >= dep[x]) y = anc[y][j];
    if(x == y) return x;

    for(int j = 19; j >= 0; --j) if(anc[y][j] != anc[x][j]) y = anc[y][j], x = anc[x][j];
    return anc[x][0];
}

int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }

    for(int i = 0; i < k; ++i) cin >> a[i], q.push(a[i]), nearer[a[i]] = 1;

    while(!q.empty()){
        int node = q.front();
        q.pop();

        for(auto i : adj[node]) if(!nearer[i]) q.push(i), nearer[i] = nearer[node] + 1;
    }

    dep[1] = 1;
    dfs(1, 0);
    for(int j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1];

    for(int mask = 1; mask < (1 << k); ++mask){
        vector <int> v;
        for(int i = 0; i < k; ++i) if((mask >> i) & 1) v.pb(a[i]);

        int x = v[0];
        for(int i = 1; i < v.size(); ++i) x = lca(x, v[i]);

        vector <int> d; int mn = inf, mx = 0;
        for(auto i : v){
            d.pb(dist(i, x));
            mn = min(mn, d.back());
            mx = max(mx, d.back());
        }

        int diff = (mx + mn) / 2;
        for(int i = 0; i < v.size(); ++i) if(d[i] == mx){
            x = v[i];
            for(int j = 19; j >= 0; --j) if((diff >> j) & 1) x = anc[x][j];
            break;
        }

        bool ok = (nearer[x] == diff + 1);
        for(auto i : v) if(dist(x, i) != diff) ok = 0;

        if(ok) dp[mask] = 1, pos[mask] = x;
        else dp[mask] = inf;

        for(int sub = mask; sub; sub = (sub - 1) & mask) if(dp[sub] + dp[mask ^ sub] < dp[mask]){
            dp[mask] = dp[sub] + dp[mask ^ sub];
            from[mask] = {sub, (mask ^ sub)};
        }
    }

    vector <int> v = {(1 << k) - 1};

    while(v.size()){
        int x = v.back();
        v.pop_back();

        if(from[x].F){
            v.pb(from[x].F);
            v.pb(from[x].S);
        }
        else ans.pb(pos[x]);
    }

    cout << ans.size() << endl;
    for(auto i : ans) cout << i << " ";
    cout << endl;
    return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 1; i < v.size(); ++i) x = lca(x, v[i]);
      |                        ~~^~~~~~~~~~
pastiri.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < v.size(); ++i) if(d[i] == mx){
      |                        ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 104012 KB Output is correct
2 Execution timed out 1089 ms 104356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 13096 KB Output is correct
2 Correct 66 ms 12908 KB Output is correct
3 Correct 673 ms 80460 KB Output is correct
4 Correct 661 ms 82752 KB Output is correct
5 Correct 776 ms 79852 KB Output is correct
6 Correct 803 ms 82800 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12372 KB Integer 0 violates the range [1, 2000]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 73704 KB Time limit exceeded
2 Halted 0 ms 0 KB -