oj.uz

Submission #854146

# Submission time Handle Problem Language Result Execution time Memory
854146 2023-09-26T08:43:08 Z 8pete8 Village (BOI20_village) C++17
12 / 100
 2 ms 6744 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=25,root=1000,inf=1e18;
vector<int>adj[mxn+10];
int subsize[mxn+10],n;
int ansmn[mxn+10],ansmx[mxn+10],up[mxn+10][lg+10],h[mxn+10];
stack<int>sub;
int ans2=0,ans1=0;
bool cmp(int a,int b){return subsize[a]>subsize[b];}
void build(int cur,int p){
    subsize[cur]=1;
    for(auto i:adj[cur]){
        if(i==p)continue;
        build(i,cur);
        ans2+=min(subsize[i],n-subsize[i]);//we claim we can achive this
        subsize[cur]+=subsize[i];
    }
}
int getcen(int cur,int p){
    for(auto i:adj[cur]){
        if(i==p)continue;
        if(subsize[i]*2>n)return getcen(i,cur);
    }
    return cur;
}
void dfs(int cur,int p){
    sub.push(cur);
    for(auto i:adj[cur]){
        if(i==p)continue;
        dfs(i,cur);
    }
}
int solvemn(int cur,int p){
    vector<int>v;
    for(auto i:adj[cur]){
        if(i==p)continue;
        if(solvemn(i,cur))v.pb(i);
    }
    if(v.size()){
        ans1++;
        ansmn[cur]=v[0];
        for(int i=0;i<v.size()-1;i++)ansmn[v[i]]=v[i+1],ans1+=2;
        ansmn[v[v.size()-1]]=cur;
        ans1++;
    }
    else return 1;
    return 0;
}
void solvemx(){
    int node=getcen(1,-1);
    stack<int>st;
    sort(all(adj[node]),cmp);
    for(auto i:adj[node]){
        dfs(i,node);
        int k=st.size();
        k=min(k,subsize[i]);
        for(int j=0;j<k;j++){
            ansmx[sub.top()]=st.top();
            ansmx[st.top()]=sub.top();
            sub.pop();
            st.pop();
        }
        while(!sub.empty()){
            st.push(sub.top());
            sub.pop();
        }
    }
    if(st.size()){
        ansmx[node]=st.top();
        ansmx[st.top()]=node;
        return;
    }
    int g=1;
    if(node==1)g=2;
    ansmx[node]=g;
    ansmx[ansmx[g]]=node;
    //for(auto i:sub)cout<<i<<"\n";
}
int32_t main(){
    fastio
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    build(1,-1);
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    solvemx();
    if(solvemn(1,-1)){
        int node=adj[1][0];
        ansmn[1]=node;
        int next=ansmn[node];
        while(ansmn[next]!=node)next=ansmn[next];
        ansmn[next]=1;
        ans1+=2;
    }
    cout<<ans1<<' '<<ans2*2<<'\n';
    for(int i=1;i<=n;i++)cout<<ansmn[i]<<" ";
    cout<<'\n';
    for(int i=1;i<=n;i++)cout<<ansmx[i]<<" ";
}

Compilation message

Village.cpp: In function 'long long int solvemn(long long int, long long int)':
Village.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0;i<v.size()-1;i++)ansmn[v[i]]=v[i+1],ans1+=2;
      |                     ~^~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 2 ms 6488 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 2 ms 6488 KB Output is correct
17 Correct 2 ms 6488 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Integer parameter [name=vi] equals to 0, violates the range [1, 256]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 2 ms 6488 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 2 ms 6488 KB Output is correct
17 Correct 2 ms 6488 KB Output is correct
18 Incorrect 2 ms 6488 KB Integer parameter [name=vi] equals to 0, violates the range [1, 256]
19 Halted 0 ms 0 KB -