Submission #418828

#	Time	Username	Problem	Language	Result	Execution time	Memory
418828		ly20	Village (BOI20_village)	C++17	100 / 100	132 ms	20492 KiB

Village

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN];
long long mn, mx;
int rmn[MAXN], rmx[MAXN];
int cur[MAXN];
int grau[MAXN];
int marc[MAXN];
int dist[MAXN];
int sub[MAXN];
int n;
vector <int> cmp[MAXN];
int cm;
void dfs(int v, int p) {
    sub[v] = 1;
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i];
        if(viz == p) continue;
        dfs(viz, v);
        sub[v] += sub[viz];
    }
    mx += min(sub[v], n - sub[v]);
    //printf("%d\n", sub[v]);
}
int dfs2(int v, int p) {
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i];
        if(viz == p) continue;
        if(sub[viz] > n / 2) return dfs2(viz, v);
    }
    return v;
}
void dfs3(int v, int p) {
    cmp[cm].push_back(v);
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i];
        if(viz == p) continue;
        dfs3(viz, v);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        grafo[a].push_back(b);
        grafo[b].push_back(a);
        grau[a]++; grau[b]++;
    }
    queue <int> fila;
    for(int i = 1; i <= n; i++) {
            rmn[i] = i; rmx[i] = i;
        if(grau[i] == 1) fila.push(i);
    }
    while(!fila.empty()) {
        int cur = fila.front(); fila.pop();
        marc[cur] = 1;
        int p = grafo[cur][0];
        for(int i = 0 ;i < grafo[cur].size(); i++) {
            int viz = grafo[cur][i];
            grau[viz]--;
            if(grau[viz] == 1) fila.push(viz);
            if(marc[viz] == 0) p = viz;
        }
        if(rmn[cur] == cur) {
            swap(rmn[cur], rmn[p]);
            mn += 2;
        }
    }
    dfs(1, 1);
    int cn = dfs2(1, 1);
    for(int i = 0; i < grafo[cn].size(); i++) {
        dfs3(grafo[cn][i], cn);
        cm++;
    }
    int mt = 1123456789;
    int id = 0;
    for(int i = 0; i < cm; i++) {
        if(cmp[i].size() < mt) {
            mt = cmp[i].size();
            id = i;
        }
    }
    if(n % 2 == 0) cmp[id].push_back(cn);
    vector <int> temp;
    for(int i = 0; i < cm; i++) {
        for(int j = 0; j < cmp[i].size(); j++) temp.push_back(cmp[i][j]);
    }
    for(int i = 0; i < temp.size() / 2; i++) {
        int pr = i + temp.size() / 2;
        swap(rmx[temp[i]], rmx[temp[pr]]);
    }
    if(n % 2 == 1) swap(rmx[temp[0]], rmx[cn]);
    printf("%lld %lld\n", mn, mx * 2);
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmn[i]);
    }
    printf("\n");
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmx[i]);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'int dfs2(int, int)':
Village.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'void dfs3(int, int)':
Village.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i = 0 ;i < grafo[cur].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
Village.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < grafo[cn].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
Village.cpp:80:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(cmp[i].size() < mt) {
      |            ~~~~~~~~~~~~~~^~~~
Village.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j = 0; j < cmp[i].size(); j++) temp.push_back(cmp[i][j]);
      |                        ~~^~~~~~~~~~~~~~~
Village.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0; i < temp.size() / 2; i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
Village.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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