Submission #1036871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036871		MarwenElarbi	Village (BOI20_village)	C++17	0 / 100	1 ms	2904 KiB

Village

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")*/
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
int sz[nax];
vector<int> a;
long long ans=0;
int n;
vi adj[nax];
void dfs(int x,int p){
    //cout <<x<<" "<<" "<<p<<endl;
    sz[x]=1;
    a.pb(x);
    for(auto u:adj[x]){
        //cout <<u<<endl;
        if(u==p) continue;
        
        dfs(u,x);
        sz[x]+=sz[u];
    }
    ans+=2*min(sz[x],n-sz[x]);
    //cout <<x<<" "<<sz[x]<<" "<<n-sz[x]<<" "<<ans<<endl;
    return;
}
int find(int x,int p){
    for(auto u:adj[x]){
        if(u==p) continue;
        if(sz[u]*2>n) return find(u,x);
    }
    return x;
}
int main(){
    optimise;
    //setIO("dec");
    cin>>n;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(0,-1);
    //cout <<endl<<endl;
    a.clear();
    ans=0;
    for (int i = 0; i < n; ++i)
    {
        sz[i]=0;
    }
    int centroid=find(0,-1);
    dfs(centroid,-1);
    int res[n];
    for (int i = 0; i < n; ++i)
    {
        res[a[i]]=a[(i+n/2)%n];
    }
    cout <<ans<<endl;
    for (int i = 0; i < n; ++i)
    {
        cout <<res[i]+1<<" ";
    }cout <<endl;
}

Compilation message (stderr)

Village.cpp: In function 'void setIO(std::string)':
Village.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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