oj.uz

Submission #473180

# Submission time Handle Problem Language Result Execution time Memory
473180 2021-09-15T09:49:56 Z balbit Meetings 2 (JOI21_meetings2) C++14
0 / 100
 7 ms 9804 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;

vector<int> g[maxn];

int sz[maxn], L[maxn], R[maxn], par[maxn], dep[maxn];
vector<int> children[maxn]; // including self
int IT = 0;

int lca[4005][4005];

void dfs1(int v, int p) {
    par[v] = p;
    sz[v] = 1;
    L[v] = R[v] = IT++;
    children[v].pb(v);
    for (int u : g[v]) {
        if (u != p) {
            dep[u] = dep[v] + 1;
            dfs1(u,v);
            sz[v] += sz[u];
            R[v] = R[u];
            for (int c : children[u]) {
                children[v].pb(c);
            }
        }
    }
}

bool isAnc(int a, int b) {
    // is a b's ancestor?
    return L[a] <= L[b] && R[a] >= R[b];
}

int n;

vector<int> quadratic() {
    dfs1(0, -1);


    REP(i,n) {
        for (int c : children[i]) {
            lca[i][c] = lca[c][i] = i;
        }
        for (int c : g[i]) {
            if (c != par[i]) {
                for (int c2 : g[i]) {
                    if (c2 > c && c2 != par[i]) {
                        for (int v1 : children[c]) for (int v2 : children[c2]) {
                            lca[v1][v2] = lca[v2][v1] = i;
                        }
                    }
                }
            }
        }
    }

    vector<int> dst(n); // max accommodation for this length
    auto go = [&](int a, int b, int s1, int s2) {
        bug(a,b,s1,s2);
        bug(dep[a] + dep[b] - dep[lca[a][b]]*2);
        MX(dst[dep[a] + dep[b] - dep[lca[a][b]]*2], min(s1, s2) * 2);
    };

    REP(a,n) for (int j : g[a]) if (j != par[a]) {
        for (int b : children[j]) {
            go(a,b,n-sz[j],sz[b]);
        }
    }

    REP(i,n) REP(j,i) {
        int a = i, b = j;
        if (dep[a] > dep[b]) swap(a,b);
        int s1, s2;
        if (isAnc(a,b)) {
            continue;
        }
        s1 = sz[a];
        s2 = sz[b];
        go(a,b,s1,s2);
//        bug(a,b,lca[a][b], s1, s2);
//        bug(dep[a] + dep[b] - dep[lca[a][b]] * 2);

    }
    for (int i = n-2; i>=0; --i) {
        MX(dst[i], dst[i+1]);
    }
    vector<int> ret(n+1);
    int j = 1;
    for (int i = n; i>=1; --i) {
        if (i % 2 == 1) ret[i] = 1;
        else{
            while (j+1 < n && dst[j+1] >= i) {
                ++j;
            }
            ret[i] = j+1;
            bug(i, ret[i]);
        }
    }
    return ret;
}

signed main(){
    IOS();
    cin>>n;
    REP(i,n-1) {
        int a,b; cin>>a>>b; --a; --b;
        g[a].pb(b); g[b].pb(a);
    }
    vector<int> yay = quadratic();
    REP1(i,n) {
        cout<<yay[i]<<endl;
    }

}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Incorrect 7 ms 9740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Incorrect 7 ms 9740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Incorrect 7 ms 9740 KB Output isn't correct
6 Halted 0 ms 0 KB -