Submission #386845

#	Time	Username	Problem	Language	Result	Execution time	Memory
386845		BartolM	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	3594 ms	39740 KiB

meetings2

#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<18);

int n;
vector <int> ls[N], cnt[N], svi;
int dp[N], sol[N], rip[N];
int T[2*OFF];
vector <pii> v;//(vel, dub)

void update(int pos, int val) {
    for (pos+=OFF; pos; pos/=2) T[pos]=max(T[pos], val);
}

void reset(int pos) {
    for (pos+=OFF; pos; pos/=2) T[pos]=-INF;
}

int query(int a, int b,  int pos=1, int lo=0, int hi=OFF) {
    if (lo>=b || hi<=a) return -INF;
    if (lo>=a && hi<=b) return T[pos];
    int mid=(lo+hi)/2;
    return max(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
}

void calc(int node, int par) {
    dp[node]=1;
    for (int sus:ls[node]) {
        if (sus==par || rip[sus]) continue;
        calc(sus, node);
        dp[node]+=dp[sus];
    }
}

int nadji(int node, int par, int uk) {
    for (int sus:ls[node]) {
        if (sus==par || rip[sus]) continue;
        if (dp[sus]>uk/2) return nadji(sus, node, uk);
    }
    return node;
}

void ubaci(int node, int par, int d) {
    int ind_par=-1;
    for (int i=0; i<ls[node].size(); ++i) {
        int sus=ls[node][i];
        if (rip[sus]) continue;
        if (sus==par) ind_par=i;
        else ubaci(sus, node, d+1);
    }
    v.pb(mp(n-cnt[node][ind_par], d));
    svi.pb(n-cnt[node][ind_par]);
}

void rek(int node) {
    calc(node, 0);
    int cent=nadji(node, 0, dp[node]);

    #if DEBUG
        printf("\ncent =========== %d\n", cent);
    #endif // DEBUG

    svi.clear();
    for (int i=0; i<ls[cent].size(); ++i) {
        v.clear();
        int sus=ls[cent][i], siz=n-cnt[cent][i];
        if (rip[sus]) continue;
        ubaci(sus, cent, 1);

        #if DEBUG
            printf("sus: %d\n", sus);
        #endif // DEBUG

        for (pii pp:v) {
            #if DEBUG
                printf("(%d, %d) ", pp.X, pp.Y);
            #endif

            if (pp.X>=siz) sol[siz]=max(sol[siz], pp.Y+1);
            else sol[pp.X]=max(sol[pp.X], pp.Y+1);
            sol[pp.X]=max(sol[pp.X], query(pp.X, n+1)+pp.Y+1);
        }
        for (pii pp:v) update(pp.X, pp.Y);
        #if DEBUG
            printf("\n");
        #endif // DEBUG

    }
    for (int x:svi) reset(x);

    svi.clear();
    for (int i=(int)ls[cent].size()-1; i>=0; --i) {
        int sus=ls[cent][i];
        if (rip[sus]) continue;
        v.clear();
        ubaci(sus, cent, 1);
        for (pii pp:v) sol[pp.X]=max(sol[pp.X], query(pp.X, n)+pp.Y+1);
        for (pii pp:v) update(pp.X, pp.Y);
    }
    for (int x:svi) reset(x);

    rip[cent]=1;
    for (int sus:ls[cent]) if (!rip[sus]) rek(sus);
}

void prec(int node, int par) {
    dp[node]=1;
    int ind_par=-1;
    for (int i=0; i<ls[node].size(); ++i) {
        int sus=ls[node][i];
        if (sus==par) ind_par=i, cnt[node].pb(0);
        else {
            prec(sus, node);
            dp[node]+=dp[sus];
            cnt[node].pb(dp[sus]);
        }
    }
    if (ind_par>-1) cnt[node][ind_par]=n-dp[node];
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(b); ls[b].pb(a);
    }
}

int main() {
    load();
    prec(1, 0);

    #if DEBUG
        for (int i=1; i<=n; ++i) {
            printf("node: %d\nls: ", i);
            for (int sus:ls[i]) printf("%d ", sus);
            printf("\ncnt: ");
            for (int x:cnt[i]) printf("%d ", x);
            printf("\n\n");
        }
    #endif // DEBUG


    fill(T, T+2*OFF, -INF);
    rek(1);

    sol[n]=max(sol[n], 1);
    for (int i=n-1; i>=1; --i) sol[i]=max(sol[i], sol[i+1]);
    for (int i=1; i<=n; ++i) printf("%d\n", i%2 ? 1 : sol[i/2]);

    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void ubaci(int, int, int)':
meetings2.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i=0; i<ls[node].size(); ++i) {
      |                   ~^~~~~~~~~~~~~~~~
meetings2.cpp: In function 'void rek(int)':
meetings2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i=0; i<ls[cent].size(); ++i) {
      |                   ~^~~~~~~~~~~~~~~~
meetings2.cpp: In function 'void prec(int, int)':
meetings2.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i=0; i<ls[node].size(); ++i) {
      |                   ~^~~~~~~~~~~~~~~~
meetings2.cpp: In function 'void load()':
meetings2.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
meetings2.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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