Submission #418825

#	Time	Username	Problem	Language	Result	Execution time	Memory
418825		ly20	Village (BOI20_village)	C++17	6 / 100	4 ms	2948 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 main() {
    int n;
    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;
        if(grau[i] == 1) fila.push(i);
    }
    while(!fila.empty()) {
        int cur = fila.front(); fila.pop();
        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(grau[viz] != 0) p = viz;
        }
        if(rmn[cur] == cur) {
            swap(rmn[cur], rmn[p]);
            mn += 2;
        }
    }
    printf("%lld %lld\n", mn, mn);
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmn[i]);
    }
    printf("\n");
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmn[i]);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:27:26: 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[cur].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
Village.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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