Submission #720758

#	Time	Username	Problem	Language	Result	Execution time	Memory
720758		n0sk1ll	Village (BOI20_village)	C++17	50 / 100	224 ms	26720 KiB

Village

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

graph g(100005);
int tin[100005],tout[100005];
int dub[100005],up[20][100005],siz[100005];
int VREME=0;

void dfs(int p, int q)
{
    tin[p]=++VREME,dub[p]=dub[q]+1,up[0][p]=q,siz[p]=1;
    for (auto it : g[p]) if (it!=q) dfs(it,p),siz[p]+=siz[it];
    tout[p]=VREME;
}

void build(int n)
{
    ff(k,1,20) fff(i,1,n) up[k][i]=up[k-1][up[k-1][i]];
}

bool anc(int a, int b)
{
    if (a==0) return true; if (b==0) return false;
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}

int Lca(int a, int b)
{
    bff(k,0,20) if (!anc(up[k][a],b)) a=up[k][a];
    if (!anc(a,b)) a=up[0][a]; return a;
}

int dist(int a, int b)
{
    return dub[a]+dub[b]-2*dub[Lca(a,b)];
}

int find_centroid(int p, int q, int n)
{
    int c=p;
    for (auto it : g[p]) if (it!=q)
    {
        int tc=find_centroid(it,p,n);
        if (tc!=-1) return tc;
        if (2*siz[it]>n) c=-1;
    }
    if (2*(n-siz[p])>n) c=-1;
    return c;
}

void poseti(int p, int q, vector<int> &dodaj)
{
    dodaj.pb(p);
    for (auto it : g[p])
        if (it!=q) poseti(it,p, dodaj);
}

///ans arrays
int vel[100005];
int mal[100005];

int main()
{
    FAST;

    int n; cin>>n;
    ff(i,1,n)
    {
        int u,v; cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
    }

    dfs(1,0),tout[1]=VREME,build(n);
    int c=find_centroid(1,0,n);

    ///veliki

    vector<int> cor,big;
    for (auto it : g[c])
    {
        if (2*max(siz[it],n-siz[it])<n) poseti(it,c,cor);
        else poseti(it,c,big);
    }
    vector<int> border;
    border.pb(c);
    for (auto it : cor) border.pb(it);
    for (auto it : big) border.pb(it);
    ff(i,0,n) vel[border[i]]=border[(i+n/2)%n];

    ///mali

    fff(i,1,n) mal[i]=i+1;
    mal[n]=1;

    ///answer

    li malans=0,velans=0;
    fff(i,1,n) malans+=dist(i,mal[i]);
    fff(i,1,n) velans+=dist(i,vel[i]);

    cout<<malans<<" "<<velans<<"\n";
    fff(i,1,n) cout<<mal[i]<<" "; cout<<"\n";
    fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
}

//Note to self: Check for overflow

Compilation message (stderr)

Village.cpp: In function 'bool anc(int, int)':
Village.cpp:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |     if (a==0) return true; if (b==0) return false;
      |     ^~
Village.cpp:56:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |     if (a==0) return true; if (b==0) return false;
      |                            ^~
Village.cpp: In function 'int Lca(int, int)':
Village.cpp:63:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |     if (!anc(a,b)) a=up[0][a]; return a;
      |     ^~
Village.cpp:63:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |     if (!anc(a,b)) a=up[0][a]; return a;
      |                                ^~~~~~
Village.cpp: In function 'int main()':
Village.cpp:13:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   13 | #define fff(i,a,b) for (int i = a; i <= b; i++)
      |                    ^~~
Village.cpp:135:5: note: in expansion of macro 'fff'
  135 |     fff(i,1,n) cout<<mal[i]<<" "; cout<<"\n";
      |     ^~~
Village.cpp:135:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  135 |     fff(i,1,n) cout<<mal[i]<<" "; cout<<"\n";
      |                                   ^~~~
Village.cpp:13:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   13 | #define fff(i,a,b) for (int i = a; i <= b; i++)
      |                    ^~~
Village.cpp:136:5: note: in expansion of macro 'fff'
  136 |     fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
      |     ^~~
Village.cpp:136:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  136 |     fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
      |                                   ^~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50