제출 #473225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
473225		balbit	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	757 ms	62628 KiB

meetings2

#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 int inf = 1e9;
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 dfsqua(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;
            dfsqua(u,v);
            sz[v] += sz[u];
            R[v] = R[u];
            for (int c : children[u]) {
                children[v].pb(c);
            }
        }
    }
}

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

vector<int> ord;
bool alive[maxn];

struct S{
    int a, b, ab, bc, abc;
}s[400005 * 4];

S pull(S x, S y){
    S r;
    r.a=max(x.a, y.a);
    r.b=max(x.b, y.b);
    r.ab=max(x.ab,y.ab);
    r.bc=max(x.bc,y.bc);
    r.abc=max(x.abc,y.abc);
    MX(r.ab, x.a+y.b);
    MX(r.bc, x.b+y.a);
    MX(r.abc, x.ab+y.a);
    MX(r.abc, x.a+y.bc);
    return r;
}

void MO(int p, bool on, int o=1, int l=0, int r=SZ(ord)-1) {
    if (l > p || r < p) return;
    if (l == r) {
        int a = ord[l];
        if (on) {
            s[o] = {
                dep[a],
                dep[a]*-2,
                -dep[a],
                -dep[a],
                0
            };
        }else{
            s[o] = {
                -inf,
                dep[a]*-2,
                -inf,
                -inf,
                -inf
            };
        }
        return;
    }
    int mid = l+r>>1;
    MO(p,on, o*2,l,mid);
    MO(p,on, o*2+1,mid+1,r);
    s[o] = pull(s[o*2], s[o*2+1]);
}

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

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() {
    dfsqua(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 = 0;
    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;
}

int cen(int v) {
    for (int u : g[v]) {
        if (u!=par[v] && sz[u] >= (n+1)/2) {
            return cen(u);
        }
    }
    return v;
}

//int csz[maxn]; // centroid based sizes



vector<int> who[maxn];

vector<int> fast(){
    dfs(0,-1);
    int rt = cen(0), rt2 = -1;
    if (sz[rt] == n-sz[rt]) {
        rt2 = par[rt];
    }
    bug(rt, rt2);
    dep[rt] = 0;
    dfs2(rt, rt); // now everything is relative to the new root
    REP(i,n) {
        if (i != rt)
        who[sz[i]].pb(i);
    }
    vector<int> ret(n+1);

    #ifdef BALBIT
    for (int x : ord) cout<<x<<' ';
    cout<<endl;
    #endif

    REP(i, SZ(ord)) {
        MO(i, 0);
    }
    REP(i,n) {
        MO(L[i], 1);
    }

    for (int i = 1; i<=n; ++i ) {
        if (i & 1) {
            ret[i] = 1;
        }else{
            bug(i, s[1].abc+1);
            ret[i] = s[1].abc+1;
            for (int x : who[i/2]) {
                MO(L[x], 0);
            }
        }
    }
    for (int t : g[rt]) {
        bug(t, sz[t]);
        MX(ret[sz[t] * 2], 2);
    }
    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 = fast();
    REP1(i,n) {
        cout<<yay[i]<<endl;
    }

}

컴파일 시 표준 에러 (stderr) 메시지

meetings2.cpp: In function 'void MO(int, bool, int, int, int)':
meetings2.cpp:138:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     int mid = l+r>>1;
      |               ~^~
meetings2.cpp: In function 'std::vector<int> fast()':
meetings2.cpp:250:22: warning: variable 'rt2' set but not used [-Wunused-but-set-variable]
  250 |     int rt = cen(0), rt2 = -1;
      |                      ^~~

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80