oj.uz

Submission #427311

# Submission time Handle Problem Language Result Execution time Memory
427311 2021-06-14T14:13:05 Z Osama_Alkhodairy Meetings 2 (JOI21_meetings2) C++17
0 / 100
 7 ms 6580 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 200001;

int n, sz[N], blocked[N], tree[2 * N];
vector <int> v[N], ans;
vector <pair <int, int> > c;

void update(int p, int v, int d){
    p += n + 1;
    if(d == 1) tree[p] = v;
    else tree[p] = max(tree[p], v);
    for(; p > 1 ; p >>= 1){
        tree[p >> 1] = max(tree[p], tree[p ^ 1]);
    }
}
int query(int l, int r){
    r++;
    int ret = 0;
    for(l += n + 1, r += n + 1 ; l < r ; l >>= 1, r >>= 1){
        if(l & 1) ret = max(ret, tree[l++]);
        if(r & 1) ret = max(ret, tree[--r]);
    }
    return ret;
}
void dfsz(int node, int pnode){
    sz[node] = 1;
    for(auto &i : v[node]){
        if(i == pnode || blocked[i]) continue;
        dfsz(i, node);
        sz[node] += sz[i];
    }
}
int find(int node, int pnode, int n){
    for(auto &i : v[node]){
        if(i != pnode && !blocked[i] && 2 * sz[i] > n){
            return find(i, node, n);
        }
    }
    return node;
}
void dfs(int node, int pnode, int len){
    c.push_back(make_pair(sz[node], len));
    for(auto &i : v[node]){
        if(i == pnode || blocked[i]) continue;
        dfs(i, node, len + 1);
    }
}
void solve(int node){
    dfsz(node, 0);
    int cen = find(node, 0, sz[node]);
    dfsz(cen, 0);
    for(int itt = 0 ; itt < 2 ; itt++){
        vector <pair <int, int> > all;
        for(auto &i : v[cen]){
            if(blocked[i]) continue;
            c.clear();
            dfs(i, cen, 1);
            for(auto &j : c){
                int mx = query(j.first, n);
                if(mx > 0) ans[j.first] = max(ans[j.first], j.second + mx);
            }
            for(auto &j : c){
                update(j.first, j.second, 0);
                ans[min(j.first, sz[cen] - sz[i])] = max(ans[min(j.first, sz[cen] - sz[i])], j.second);
                all.push_back(j);
            }
        }
        for(auto &i : all){
            update(i.first, 0, 1);
        }
        memset(tree, 0, sizeof tree);
        reverse(v[node].begin(), v[node].end());
    }
    blocked[cen] = 1;
    for(auto &i : v[cen]){
        if(blocked[i]) continue;
        solve(i);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0 ; i < n - 1 ; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ans.resize(n + 1);
    solve(1);
    for(int i = n ; i > 1 ; i--){
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }
    for(int i = 1 ; i <= n ; i++){
        if(i % 2) cout << "1\n";
        else cout << ans[i / 2] + 1 << "\n";
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6476 KB Output is correct
2 Correct 5 ms 6512 KB Output is correct
3 Correct 7 ms 6476 KB Output is correct
4 Correct 7 ms 6580 KB Output is correct
5 Correct 6 ms 6476 KB Output is correct
6 Incorrect 7 ms 6476 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6476 KB Output is correct
2 Correct 5 ms 6512 KB Output is correct
3 Correct 7 ms 6476 KB Output is correct
4 Correct 7 ms 6580 KB Output is correct
5 Correct 6 ms 6476 KB Output is correct
6 Incorrect 7 ms 6476 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6476 KB Output is correct
2 Correct 5 ms 6512 KB Output is correct
3 Correct 7 ms 6476 KB Output is correct
4 Correct 7 ms 6580 KB Output is correct
5 Correct 6 ms 6476 KB Output is correct
6 Incorrect 7 ms 6476 KB Output isn't correct
7 Halted 0 ms 0 KB -