Submission #915853

#	Time	Username	Problem	Language	Result	Execution time	Memory
915853		Alcabel	Prize (CEOI22_prize)	C++17	54 / 100	3610 ms	397052 KiB

Main

#pragma GCC optimize("O3", "Ofast")
#pragma GCC optimize("avx", "avx2")
#include <bits/stdc++.h>
using namespace std;
 
struct DSU {
    int n;
    vector<int> par;
    DSU() {}
    DSU(int _n) {
        n = _n;
        par.resize(n);
        clear();
    }
    void clear() {
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    void uniteSets(int v, int u) {
        v = getParent(v), u = getParent(u);
        if (v == u) {
            return;
        }
        par[u] = v;
    }
    ~DSU() {}
};
 
const int maxn = 1e6;
vector<int> g1[maxn], g2[maxn];
int tin1[maxn], tout1[maxn], tin2[maxn], tout2[maxn], tt;
 
void dfs1(int v) {
    tin1[v] = tt++;
    for (const int& u : g1[v]) {
        dfs1(u);
    }
    tout1[v] = tt++;
}
 
vector<int> vset;
 
void dfs2(int v, int k) {
    tin2[v] = tt++;
    // cerr << "v: " << v + 1 << '\n';
    if ((int)vset.size() < k) {
        // cerr << "hui\n";
        vset.emplace_back(v);
    }
    for (const int& u : g2[v]) {
        dfs2(u, k);
    }
    tout2[v] = tt++;
}
 
vector<pair<int, int>> queries[maxn];
const int maxq = 1e5;
int ans[maxq];
DSU dsu;
 
void dfsAns1(int v) {
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = dsu.getParent(queries[v].back().first);
        queries[v].pop_back();
    }
    for (const int& u : g1[v]) {
        dfsAns1(u);
        dsu.uniteSets(v, u);
    }
}
 
void dfsAns2(int v) {
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = dsu.getParent(queries[v].back().first);
        queries[v].pop_back();
    }
    for (const int& u : g2[v]) {
        dfsAns2(u);
        dsu.uniteSets(v, u);
    }
}
 
vector<pair<int, int>> w1[maxn], w2[maxn];
char vis[maxn];
int dist1[maxn], dist2[maxn];
 
void dfsCalc1(int v) {
    // cerr << "v: " << v + 1 << ", dist1: " << dist1[v] << '\n';
    vis[v] = tt;
    for (const auto [u, delta] : w1[v]) {
        if (vis[u] < tt) {
            dist1[u] = dist1[v] + delta;
            dfsCalc1(u);
        }
    }
}
 
void dfsCalc2(int v) {
    // cerr << "v: " << v + 1 << ", dist2: " << dist2[v] << '\n';
    vis[v] = tt;
    for (const auto& [u, delta] : w2[v]) {
        if (vis[u] < tt) {
            dist2[u] = dist2[v] + delta;
            dfsCalc2(u);
        }
    }
}
 
void solve() {
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    int root1 = -1, root2 = -1;
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        if (p != -2) {
            g1[p].emplace_back(i);
        } else {
            root1 = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        if (p != -2) {
            g2[p].emplace_back(i);
        } else {
            root2 = i;
        }
    }
    tt = 0;
    dfs1(root1);
    tt = 0;
    dfs2(root2, k);
    for (const int& v : vset) {
        cout << v + 1 << ' ';
    }
    cout << endl;
    sort(vset.begin(), vset.end(), [&](const int& A, const int& B) {
        return tin1[A] < tin1[B];
    });
    dsu = DSU(n);
    for (int i = 0; i < k - 1; ++i) {
        int v = vset[i], u = vset[i + 1];
        // cerr << "v: " << v + 1 << ", u: " << u + 1 << '\n';
        queries[u].emplace_back(v, i);
    }
    dfsAns1(root1);
    int comproot1 = -1;
    vector<int> lca1(k - 1);
    for (int i = 0; i < k - 1; ++i) {
        lca1[i] = ans[i];
        // cerr << "i: " << i << ", lca1: " << lca1[i] + 1 << '\n';
        if (comproot1 == -1 || tin1[comproot1] > tin1[ans[i]]) {
            comproot1 = ans[i];
        }
        int v = vset[i], u = vset[i + 1];
        if (tin2[v] > tin2[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    dsu.clear();
    dfsAns2(root2);
    int comproot2 = -1;
    vector<int> lca2(k - 1);
    for (int i = 0; i < k - 1; ++i) {
        lca2[i] = ans[i];
        // cerr << "i: " << i << ", lca2: " << lca2[i] + 1 << '\n';
        if (comproot2 == -1 || tin2[comproot2] > tin2[ans[i]]) {
            comproot2 = ans[i];
        }
    }
    for (int i = 0; i < k - 1; ++i) {
        cout << "? " << vset[i] + 1 << ' ' << vset[i + 1] + 1 << '\n';
    }
    cout << "!" << endl;
    for (int i = 0; i < k - 1; ++i) {
        int v = vset[i], u = vset[i + 1];
        int d1v, d1u, d2v, d2u;
        cin >> d1v >> d1u >> d2v >> d2u;
        w1[lca1[i]].emplace_back(v, d1v);
        w1[lca1[i]].emplace_back(u, d1u);
        w1[v].emplace_back(lca1[i], -d1v);
        w1[u].emplace_back(lca1[i], -d1u);
        w2[lca2[i]].emplace_back(v, d2v);
        w2[lca2[i]].emplace_back(u, d2u);
        w2[v].emplace_back(lca2[i], -d2v);
        w2[u].emplace_back(lca2[i], -d2u);
    }
    dist1[comproot1] = 0;
    tt = 1;
    dfsCalc1(comproot1);
    dist2[comproot2] = 0;
    ++tt;
    dfsCalc2(comproot2);
    vector<pair<int, int>> toAsk(t);
    for (int i = 0; i < t; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        toAsk[i] = {v, u};
        if (tin1[v] > tin1[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    vector<int> part1(t), part2(t);
    dsu.clear();
    dfsAns1(root1);
    for (int i = 0; i < t; ++i) {
        // cerr << "i: " << i << ", lca1: " << ans[i] + 1 << '\n';
        auto [v, u] = toAsk[i];
        part1[i] = -2ll * dist1[ans[i]] + dist1[v] + dist1[u];
        if (tin2[v] > tin2[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    dsu.clear();
    dfsAns2(root2);
    for (int i = 0; i < t; ++i) {
        // cerr << "i: " << i << ", lca2: " << ans[i] + 1 << '\n';
        auto [v, u] = toAsk[i];
        part2[i] = -2ll * dist2[ans[i]] + dist2[v] + dist2[u];
        cout << part1[i] << ' ' << part2[i] << '\n';
    }
    cout << endl;
}
 
int main() {
    /*ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
 
#ifdef LOCALa
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif
 
    return 0;
}

Compilation message (stderr)

Main.cpp:2:35: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx", "avx2")
      |                                   ^
Main.cpp:2:35: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
Main.cpp:9:9: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
    9 |     DSU() {}
      |         ^
Main.cpp:9:9: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:10:15: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   10 |     DSU(int _n) {
      |               ^
Main.cpp:10:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:15:16: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   15 |     void clear() {
      |                ^
Main.cpp:15:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:20:24: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   20 |     int getParent(int v) {
      |                        ^
Main.cpp:20:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:26:32: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   26 |     void uniteSets(int v, int u) {
      |                                ^
Main.cpp:26:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:33:10: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   33 |     ~DSU() {}
      |          ^
Main.cpp:33:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:40:16: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   40 | void dfs1(int v) {
      |                ^
Main.cpp:40:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:50:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   50 | void dfs2(int v, int k) {
      |                       ^
Main.cpp:50:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:68:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   68 | void dfsAns1(int v) {
      |                   ^
Main.cpp:68:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:79:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   79 | void dfsAns2(int v) {
      |                   ^
Main.cpp:79:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:94:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   94 | void dfsCalc1(int v) {
      |                    ^
Main.cpp:94:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:105:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  105 | void dfsCalc2(int v) {
      |                    ^
Main.cpp:105:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:116:12: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  116 | void solve() {
      |            ^
Main.cpp:116:12: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp: In function 'void solve()':
Main.cpp:148:66: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  148 |     sort(vset.begin(), vset.end(), [&](const int& A, const int& B) {
      |                                                                  ^
Main.cpp:148:66: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp: At global scope:
Main.cpp:240:10: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  240 | int main() {
      |          ^
Main.cpp:240:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24