답안 #546661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546661 2022-04-08T02:10:12 Z Olympia Village (BOI20_village) C++17
0 / 100
1 ms 340 KB
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")


using namespace std;

vector<vector<int>> adj;
vector<int> ord;
int t = 0;
int c = 0;
vector<int64_t> pre, post, depth, sub;
vector<vector<int>> dp;

bool isAncestor(int u, int v) {
    return (pre[u] <= pre[v] && post[u] >= post[v]);
}

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;
    for (int i = 19; i >= 0; i--) if (!isAncestor(dp[u][i], v))u = dp[u][i];
    return dp[u][0];
}

void find_sub(int curNode, int prevNode) {
    sub[curNode] = 1;
    for (int i: adj[curNode]) {
        if (i != prevNode) {
            find_sub(i, curNode);
            sub[curNode] += sub[i];
        }
    }
}

int get_centroid(int curNode, int prevNode) {
    for (int i: adj[curNode]) {
        if (i == prevNode) continue;
        if (sub[i] > (int) adj.size() / 2) {
            return get_centroid(i, curNode);
        }
    }
    return curNode;
}

void f(int curNode, int prevNode) {
    depth[curNode] = depth[prevNode] + 1;
    dp[curNode].resize(20);
    dp[curNode][0] = prevNode;
    for (int i = 1; i < 20; i++)dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1];
    ord[curNode] = t++, pre[curNode] = c++;
    for (int i:adj[curNode]) if (i != prevNode)f(i, curNode);
    post[curNode] = c++;
}

vector<int> ans;
int tot = 0;
void dfs (int curNode, int prevNode) {
    //cout << curNode << " " << prevNode << endl;
    for (int i: adj[curNode]) {
        if (i == prevNode) {
            continue;
        }
        dfs(i, curNode);
        if (ans[curNode] == -1 && ans[i] == -1) {
            ans[curNode] = i;
            ans[i] = curNode;
            tot++;
        } else if (ans[i] == -1){
            ans[i] = ans[curNode];
            ans[curNode] = i;
            tot++;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    adj.resize(n), depth.assign(n, false), dp.resize(n), pre.resize(n), post.resize(n), sub.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    find_sub(0, -1);
    ord.resize(n), ans.assign(n, -1);
    int centroid = get_centroid(0, -1);
    f(centroid, centroid);
    dfs(0, -1);

    if (ans[0] == -1) {
        ans[0] = ans[adj[0].back()];
        ans[adj[0].back()] = 0;
        tot++;
    }

    int64_t al = 0;
    map<int, int> myMap;
    for (int i = 0; i < ord.size(); i++) myMap[ord[i]] = i;
    vector<int> ansr(n);
    for (int i = 0; i < n; i++) ansr[myMap[i]] = myMap[(i + n / 2 + n) % n];
    for (int i = 0; i < n; i++) al += depth[i] + depth[ansr[i]] - 2 * depth[lca(i, ansr[i])];
    cout << al << " " << tot * 2 << '\n';
    for (int i: ansr) cout << i + 1 << ' ';
    cout << '\n';
    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << ' ';
    }


}

Compilation message

Village.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("O3")
      | 
Village.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   19 | #pragma GCC optimization ("unroll-loops")
      | 
Village.cpp: In function 'int main()':
Village.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < ord.size(); i++) myMap[ord[i]] = i;
      |                     ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -