Submission #893451

#	Time	Username	Problem	Language	Result	Execution time	Memory
893451		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	100 ms	1360 KiB

meetings2

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag=false;
    if(x>y) {x=y;flag|=true;}
    return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag=false;
    if (x<y) {x=y;flag|=true;}
    return flag;
}
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e9+7;
const ll mod=1e9+7;
const ll N=4e3+5;
const ld eps=1e-9;
vector<vll> g(N),g2(N);
ll d[N],sz[N],p[N];
ll n;
ll tin[N],tout[N];
void dfs_sz(ll v){
    sz[v]=1;
    for(auto i : g[v]){
        if(i==p[v]) continue;
        d[i]=d[v]+1;
        p[i]=v;
        dfs_sz(i);
        sz[v]+=sz[i];
    }
}
ll find_cen(ll v){
    for(auto i : g[v]){
        if(d[v]>d[i]) continue;
        if(sz[i]>n/2){
            return find_cen(i);
        }
    }
    return v;
}
ll d2[N];
void dfs(ll v){
    for(auto i : g2[v]){
        if(d2[i]<d2[v]) continue;
        d2[i]=d2[v]+1;
        dfs(i);
    }
}
ll dia(ll r){
    memset(d2,0x3f,sizeof(d2));
    d2[r]=0;
    dfs(r);
    ll mx=0;
    for(ll i=1;i<=n;i++){
        if(g2[i].size()){
            if(chmax(mx,d2[i])){
                r=i;
            }
        }
    }
    memset(d2,0x3f,sizeof(d2));
    d2[r]=0;
    dfs(r);
    mx=0;
    for(ll i=1;i<=n;i++){
        if(g2[i].size()){
            chmax(mx,d2[i]);
        }
    }
    return mx;
}
void solve(){
	ll i,j;
	ll a,b;
    cin>>n;
    for(i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs_sz(1);
    ll r=find_cen(1);
    d[r]=1;
    memset(p,0,sizeof(p));
    dfs_sz(r);
    vector<vll> v(n+5);
    for(i=1;i<=n;i++){
        v[sz[i]].pb(i);
    }
    ll ans[n+5];
    ll mx=0,mx2=0;
    for(i=n/2;i>0;i--){
        for(auto j : v[i]){
            g2[j].pb(p[j]);
            g2[p[j]].pb(j);
        }
        if(g2[r].size()==0){
            ans[i*2]=1;
        }else{
            ans[i*2]=dia(r)+1;
        }
    }
    for(i=1;i<=n;i++){
        if(i%2) cout<<1<<endl;
        else cout<<ans[i]<<endl;
    }
}
signed main(){
	start();
    ll t=1;
	//cin>>t;
    while(t--) solve();
    return 0;
}
/*






*/

Compilation message (stderr)

meetings2.cpp: In function 'void solve()':
meetings2.cpp:103:7: warning: unused variable 'j' [-Wunused-variable]
  103 |  ll i,j;
      |       ^
meetings2.cpp:121:8: warning: unused variable 'mx' [-Wunused-variable]
  121 |     ll mx=0,mx2=0;
      |        ^~
meetings2.cpp:121:13: warning: unused variable 'mx2' [-Wunused-variable]
  121 |     ll mx=0,mx2=0;
      |             ^~~
meetings2.cpp: In function 'void fre(std::string)':
meetings2.cpp:38:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:38:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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