Submission #720820

#	Time	Username	Problem	Language	Result	Execution time	Memory
720820		n0sk1ll	Village (BOI20_village)	C++14	100 / 100	224 ms	26640 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];

void mfs(int p, int q)
{
    for (auto it : g[p]) if (it!=q) mfs(it,p);
    vector<int> spajam;
    for (auto it : g[p]) if (it!=q) if (siz[it]%2==1) spajam.pb(it);
    if (siz[p]%2==0) spajam.pb(p);

    for (int i=1;i<(int)spajam.size();i+=2)
        mal[spajam[i]]=spajam[i-1],mal[spajam[i-1]]=spajam[i];
}

bool vis[100005];
int deg[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;

    queue<int> bfs;
    fff(i,1,n) if ((int)g[i].size()==1) bfs.push(i);
    fff(i,1,n) deg[i]=(int)g[i].size();

    while (!bfs.empty())
    {
        int p=bfs.front(); bfs.pop();
        if (vis[p]) continue; vis[p]=1;

        for (auto it : g[p]) if (!vis[it])
        {
            if (mal[p]==p) swap(mal[p],mal[it]);
            deg[it]--; if (deg[it]==1) bfs.push(it);
        }
    }

    fff(i,1,n) if (mal[i]==i)
    {
        swap(mal[i],mal[g[i][0]]);
    }

    ///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

/*

9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

7
7 3
4 7
1 7
7 2
5 7
7 6


*/

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:148:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  148 |         if (vis[p]) continue; vis[p]=1;
      |         ^~
Village.cpp:148:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  148 |         if (vis[p]) continue; vis[p]=1;
      |                               ^~~
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:169:5: note: in expansion of macro 'fff'
  169 |     fff(i,1,n) cout<<mal[i]<<" "; cout<<"\n";
      |     ^~~
Village.cpp:169:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  169 |     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:170:5: note: in expansion of macro 'fff'
  170 |     fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
      |     ^~~
Village.cpp:170:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  170 |     fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
      |                                   ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50