Submission #1213981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213981		modwwe	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	5192 KiB

meetings2

//#include "sphinx.h"
#include<bits/stdc++.h>
#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
//#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf=1e12;
const ll mod2 =998244353;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,en,last=0;
ll el = 19;
main()
{
    ///top1apio
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    ///top1apio
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ///top1apio
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
//   cin>>s1;
    //ll t;cin>>t;while(t--)
    phongbeo(),down
    ///  checktime
    ///top1apio
}
int in[200001],ou[200001],sz[200001],dep[200001],st[17][200001],ans[200001];
vector<int> v[200001];
void dfs(int x,int y)
{
    in[x]=++dem;
    dep[x]=dep[y]+1;
    sz[x]=1;
    st[0][x]=y;
    for(auto f:v[x])
        if(f^y)
            dfs(f,x),
                sz[x]+=sz[f];
    ou[x]=dem;
}
bool check(int x,int y)
{
    if(x==0)return 1;
    if(in[x]<=in[y]&&in[y]<=ou[x])return 1;
    return 0;
}
int lca(int x,int y)
{
    if(check(x,y))return x;
    for(int i=17; i>=0; --i)
        if(!check(st[i][x],y))
            x=st[i][x];
    return st[0][x];
}
int get(int l,int r)
{
    return dep[l]+dep[r]-dep[lca(l,r)]*2;
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<n; i++)
        cin>>l>>r,v[l].pb(r),v[r].pb(l);
    s4=1;
    s5=n;
    dfs(1,0);
    for(int i=1; i<=n; i++)
        if(sz[i]>n/2&&sz[i]<s5)s4=i,s5=sz[i];
    dfs(s4,0);
    for(int i=1;i<=n;i++)
    v[i].clear();
    for(int i=1; i<=n; i++)
        v[sz[i]].pb(i);
        for(int i=1;i<=17;i++)
        for(int j=1;j<=n;j++)
    st[i][j]=st[i-1][st[i-1][j]];
    l=s4;
    r=s4;
    s4=0;
    for(int i=n/2; i>=1; --i)
    {
        for(auto x:v[i])
        {
                s2=get(l,x);
                s3=get(r,x);
                if(s2>=s3&&s2>s4)r=x;
                else if(s3>s2&&s3>s4)l=x;
                s4=max({s4,s2,s3});
        }
        ans[i]=s4+1;
    }
    for(int i=1; i<=n; i++)
        if(i%2==1)cout<<1,down
        else cout<<ans[i/2],down

            }

Compilation message (stderr)

meetings2.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main()
      | ^~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
meetings2.cpp:37:9: note: in expansion of macro 'fin'
   37 |         fin(task2);
      |         ^~~
meetings2.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
meetings2.cpp:38:9: note: in expansion of macro 'fou'
   38 |         fou(task2);
      |         ^~~
meetings2.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
meetings2.cpp:43:9: note: in expansion of macro 'fin'
   43 |         fin(task);
      |         ^~~
meetings2.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
meetings2.cpp:44:9: note: in expansion of macro 'fou'
   44 |         fou(task);
      |         ^~~

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