Submission #1102080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102080		razivo	Village (BOI20_village)	C++14	50 / 100	81 ms	22136 KiB

Village

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void dfs(int cur,int prev,vector<vector<int>> &child,vector<vector<int>> &g) {
    for(auto u : g[cur]) {
        if(u==prev) continue;
        child[cur].push_back(u);
        dfs(u,cur,child,g);
    }
}
void sw(int x,int y, vector<int> &perm) {
    swap(perm[x],perm[y]);
}
int dfs2(int cur,int per,vector<vector<int>> &child,vector<int> &perm) {
    int res = 0;
    for (int i :child[cur]) {
        res+=dfs2(i,cur,child,perm);
    }
    if(perm[cur]==cur) {sw(per,cur,perm); res+=2;}
    return res;
}
int main() {
    int n; cin>>n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int x,y; cin>>x>>y; x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<vector<int>> c(n);
    vector<int> perm(n);
    int root=0;
    for (int i = 0; i < n; ++i) {
        perm[i]=i;
        if(g[i].size()==1) root = i;
    }
    dfs(root,-1,c,g);

    cout<< dfs2(root,c[root][0],c,perm) <<" "<<1<<endl;
    for (int i = 0; i < n; ++i) {
        cout<<perm[i]+1<<" ";
    }
    cout<<endl;
    for (int i = 0; i < n; ++i) {
        cout<<perm[i]+1<<" ";
    }
    cout<<endl;
}

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