oj.uz

Submission #1102079

# Submission time Handle Problem Language Result Execution time Memory
1102079 2024-10-17T11:44:58 Z razivo Village (BOI20_village) C++14
0 / 100
 1 ms 336 KB 
#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]<<" ";
    }
    cout<<endl;
    for (int i = 0; i < n; ++i) {
        cout<<perm[i]<<" ";
    }
    cout<<endl;
}

Subtask #1
0.0 / 12.0

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

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 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 Incorrect 1 ms 336 KB Integer parameter [name=vi] equals to 0, violates the range [1, 4]
2 Halted 0 ms 0 KB -