Submission #670458

#	Time	Username	Problem	Language	Result	Execution time	Memory
670458		jamezzz	Village (BOI20_village)	C++17	50 / 100	80 ms	9840 KiB

Village

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
 
#define maxn 100005
 
int n,mnans,deg[maxn],mnpos[maxn];
vector<int> AL[maxn];

int main(){
    sf("%d",&n);
    for(int i=1;i<n;++i){
        int a,b;sf("%d%d",&a,&b);
        AL[a].pb(b);
        AL[b].pb(a);
        ++deg[a],++deg[b];
    }
    queue<int> q;
    for(int i=1;i<=n;++i){
        mnpos[i]=i;
        if(deg[i]==1)q.push(i);
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        if(mnpos[u]==u){
            int p=-1;
            for(int v:AL[u]){
                if(deg[v]!=0){
                    p=v;
                    break;
                }
            }
            if(p==-1){
                swap(mnpos[AL[u][0]], mnpos[u]);
            }
            else{
                swap(mnpos[p],mnpos[u]);
            }
            mnans+=2;
        }
        for(int v:AL[u]){
            if(deg[v]!=0){
                --deg[v],--deg[u];
                if(deg[v]<=1)q.push(v);
            }
        }
    }
    pf("%d %d\n",mnans,1);
    for(int i=1;i<=n;++i){
        pf("%d ",mnpos[i]);
    }
    pf("\n");
    for(int i=1;i<=n;++i){
        pf("%d ",mnpos[i]);
    }
    pf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     sf("%d",&n);
      |       ^
Village.cpp:21:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         int a,b;sf("%d%d",&a,&b);
      |                   ^

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