oj.uz

Submission #915853

# Submission time Handle Problem Language Result Execution time Memory
915853 2024-01-24T19:16:51 Z Alcabel Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 397052 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1954 ms 273476 KB Output is correct
2 Correct 2045 ms 277520 KB Output is correct
3 Correct 1112 ms 173504 KB Output is correct
4 Correct 1080 ms 172580 KB Output is correct
5 Correct 1150 ms 176972 KB Output is correct
6 Correct 1428 ms 194412 KB Output is correct
7 Correct 1440 ms 194808 KB Output is correct
8 Correct 1454 ms 194124 KB Output is correct
9 Correct 1159 ms 173760 KB Output is correct
10 Correct 1432 ms 175488 KB Output is correct
11 Correct 1156 ms 172204 KB Output is correct
12 Correct 1099 ms 175232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2137 ms 277988 KB Output is correct
2 Correct 1907 ms 272756 KB Output is correct
3 Correct 1114 ms 174084 KB Output is correct
4 Correct 1211 ms 176880 KB Output is correct
5 Correct 1127 ms 175052 KB Output is correct
6 Correct 1464 ms 192172 KB Output is correct
7 Correct 1606 ms 196396 KB Output is correct
8 Correct 1589 ms 196400 KB Output is correct
9 Correct 1381 ms 195080 KB Output is correct
10 Correct 1433 ms 196524 KB Output is correct
11 Correct 1312 ms 191064 KB Output is correct
12 Correct 1402 ms 195780 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1816 ms 264348 KB Output is correct
2 Correct 1792 ms 264036 KB Output is correct
3 Correct 859 ms 162648 KB Output is correct
4 Correct 925 ms 162804 KB Output is correct
5 Correct 967 ms 162848 KB Output is correct
6 Correct 1176 ms 182672 KB Output is correct
7 Correct 1302 ms 182708 KB Output is correct
8 Correct 1251 ms 182480 KB Output is correct
9 Correct 1058 ms 180508 KB Output is correct
10 Correct 1079 ms 180160 KB Output is correct
11 Correct 1068 ms 180584 KB Output is correct
12 Correct 1018 ms 180360 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3565 ms 384892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3610 ms 397052 KB Time limit exceeded
2 Halted 0 ms 0 KB -