oj.uz

답안 #805482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805482 2023-08-03T17:01:39 Z rnl42 Prize (CEOI22_prize) C++14
100 / 100
 1741 ms 301960 KB 
#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Tree {
    int root = 0;
    vector<int> parent;
    vector<vector<int>> adj;
    void resize(size_t N) {
        parent.resize(N);
        adj.resize(N);
    }
};

struct LCA {
    vector<int> first;
    vector<int> tourtree;
    vector<int> height;
    int tree_shift = 0;
    void init(Tree& t) {
        tree_shift = (1<<__lg(4*(int)t.parent.size()-1+10))+3;
        first.resize(tree_shift);
        height.resize(tree_shift);
        tourtree.assign(2*tree_shift, tree_shift-1);
        height[tree_shift-1] = 1e9;
        int tour_i = 0;
        function<void(int)> dfs = [&](const int u) {
            first[u] = tour_i;
            //dbg(u, tour_i);
            tourtree[tree_shift+tour_i++] = u;
            for (int v : t.adj[u]) {
                height[v] = height[u]+1;
                dfs(v);
                tourtree[tree_shift+tour_i++] = u;
            }
        };
        dfs(t.root);
        for (int i = tree_shift-1; i > 0; i--) {
            tourtree[i] = min(make_pair(height[tourtree[2*i]], tourtree[2*i]), make_pair(height[tourtree[2*i+1]], tourtree[2*i+1])).second;
        }
    }
    int lca(int l, int r) {
        if (first[l] > first[r]) swap(l, r);
        /*cerr << "\n-----------\n";
        for (int i = 0; i < tree_shift; i++) {
            cerr << tourtree[tree_shift+i] << " ";
        }
        cerr << "\n\n-----------\n" << endl;
        dbg(tree_shift);*/
        l = first[l]+tree_shift, r = first[r]+tree_shift+1;
        //cerr << "lr " << l << " " << r << endl;
        pair<int,int> ret(1e9, 1e9);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l&1) {
                ret = min(ret, make_pair(height[tourtree[l]], tourtree[l]));
                //dbg(tourtree[l], height[tourtree[l]]);
                l++;
            }
            if (r&1) {
                --r;
                ret = min(ret, make_pair(height[tourtree[r]], tourtree[r]));
            }
        }
        return ret.second;
    }
};

istream& operator>>(istream& in, Tree& tree) {
    for (size_t i = 0; i < tree.parent.size(); i++) {
        in >> tree.parent[i], tree.parent[i]--;
        if (tree.parent[i] == -2) {
            tree.parent[i] = -1;
            tree.root = i;
        } else {
            tree.adj[tree.parent[i]].push_back(i);
        }
    }
    return in;
}

int N, K, Q, T;
Tree trees[2];
vector<int> chosen_set;
LCA lca[2];

namespace com {
    void choose_set(vector<int>& v) {
        for (int i = 0; i < K; i++) {
            cout << v[i]+1 << (i == K-1 ? '\n' : ' ');
        }
        cout << flush;
    }
    void query(int u, int v) {
        cout << "? " << u+1 << " " << v+1 << '\n';
        Q++;
    }
    pair<vector<array<int,4>>,vector<pair<int,int>>> read_response() {
        cout << "!\n" << flush;
        vector<array<int,4>> resp(Q);
        vector<pair<int,int>> queries(T);
        for (int i = 0; i < Q; i++)
            for (int j = 0; j < 4; j++)
                cin >> resp[i][j];
        for (int i = 0; i < T; i++)
            cin >> queries[i].first >> queries[i].second, queries[i].first--, queries[i].second--;
        return make_pair(resp, queries);
    }
    void answer(int d1, int d2) {
        cout << d1 << " " << d2 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> N >> K >> Q >> T;
    Q = 0;
    for (int i = 0; i < 2; i++) {
        trees[i].resize(N);
        cin >> trees[i];
    }

    function<void(int)> dfs = [&](const int u) {
        if ((int)chosen_set.size() < K) chosen_set.push_back(u);
        for (int v : trees[0].adj[u]) dfs(v);
    };
    dfs(trees[0].root);
    sort(chosen_set.begin(), chosen_set.end());
    com::choose_set(chosen_set);
    lca[1].init(trees[1]);
    lca[0].init(trees[0]);

    sort(chosen_set.begin(), chosen_set.end(), [](const int a, const int b) {
        return lca[1].first[a] < lca[1].first[b];
    });
    vector<int> elems;
    vector<int> poselem(N, -1);
    vector<int> cumulsum = {0};
    for (int i = 0; i < K-1; i++) {
        elems.push_back(chosen_set[i]);
        poselem[elems.back()] = elems.size()-1;
        //dbg(i, elems.back());
        //dbg(chosen_set[i], chosen_set[i+1], lca[1].lca(chosen_set[i], chosen_set[i+1]));
        elems.push_back(lca[1].lca(chosen_set[i], chosen_set[i+1]));
        poselem[elems.back()] = elems.size()-1;
        //dbg(i, elems.back());
        com::query(chosen_set[i], chosen_set[i+1]);
    }
    elems.push_back(chosen_set.back());
    poselem[elems.back()] = elems.size()-1;

    /*cout << "\n\n\n";
    dbg(chosen_set);
    dbg(elems);
    cout << "\n\n\n";*/

    //vector<pair<int,int>> infotree0(N);
    //for (int i = 0; i < N; i++) infotree0[i] = make_pair(i, 0);
    //vector<int> sumuntilroot(N);
    //vector<int> w_edge(N);
    auto [resp, queries] = com::read_response();

    vector<vector<pair<int,int>>> newadj(N);
    vector<int> sumuntilroot(N, -1);
    for (int i = 0; i < Q; i++) {
        cumulsum.push_back(cumulsum.back()+resp[i][2]);
        cumulsum.push_back(cumulsum.back()-resp[i][3]);
        int a = lca[0].lca(elems[2*i], elems[2*i+2]);
        //cerr << "pair " << a << " " << elems[2*i] << " " << resp[i][0] << endl;
        newadj[a].emplace_back(elems[2*i], resp[i][0]);
        newadj[elems[2*i]].emplace_back(a, -resp[i][0]);
        newadj[a].emplace_back(elems[2*i+2], resp[i][1]);
        newadj[elems[2*i+2]].emplace_back(a, -resp[i][1]);
    }
    // à vérifier
    function<void(int)> dfs2 = [&](const int u) {
        for (auto [v, sumw] : newadj[u]) {
            if (sumuntilroot[v] == -1) {
                sumuntilroot[v] = sumuntilroot[u]+sumw;
                dfs2(v);
            }
        }
    };
    sumuntilroot[trees[0].root] = 0;
    dfs2(trees[0].root);
    /*for (int u = 0; u < N; u++) {
        if (newadj[u].size()) cerr << "sumuntil " << u << " = " << newadj[u][0].first << ":" << newadj[u][0].second << endl;
    }*/

    for (int i = 0; i < T; i++) {
        auto& q = queries[i];
        int d1 = -2*sumuntilroot[lca[0].lca(q.first, q.second)]+sumuntilroot[q.first]+sumuntilroot[q.second];
        //dbg(q.first, q.second);
        //dbg(poselem[q.first], poselem[q.second]);
        int d2 = 2*cumulsum[poselem[lca[1].lca(q.first, q.second)]]-cumulsum[poselem[q.first]]-cumulsum[poselem[q.second]];
        com::answer(d1, d2);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:190:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  190 |     auto [resp, queries] = com::read_response();
      |          ^
Main.cpp: In lambda function:
Main.cpp:206:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  206 |         for (auto [v, sumw] : newadj[u]) {
      |                   ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 917 ms 152860 KB Output is correct
2 Correct 953 ms 155032 KB Output is correct
3 Correct 710 ms 99604 KB Output is correct
4 Correct 546 ms 98824 KB Output is correct
5 Correct 658 ms 100872 KB Output is correct
6 Correct 711 ms 111292 KB Output is correct
7 Correct 762 ms 111236 KB Output is correct
8 Correct 698 ms 111032 KB Output is correct
9 Correct 562 ms 99552 KB Output is correct
10 Correct 697 ms 100416 KB Output is correct
11 Correct 597 ms 97992 KB Output is correct
12 Correct 651 ms 100048 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 887 ms 155300 KB Output is correct
2 Correct 770 ms 151984 KB Output is correct
3 Correct 674 ms 99420 KB Output is correct
4 Correct 654 ms 101308 KB Output is correct
5 Correct 599 ms 100220 KB Output is correct
6 Correct 779 ms 109424 KB Output is correct
7 Correct 808 ms 111828 KB Output is correct
8 Correct 815 ms 112124 KB Output is correct
9 Correct 722 ms 110292 KB Output is correct
10 Correct 762 ms 110912 KB Output is correct
11 Correct 679 ms 107844 KB Output is correct
12 Correct 687 ms 110660 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 653 ms 147136 KB Output is correct
2 Correct 673 ms 147152 KB Output is correct
3 Correct 446 ms 92940 KB Output is correct
4 Correct 504 ms 92844 KB Output is correct
5 Correct 407 ms 92840 KB Output is correct
6 Correct 515 ms 104152 KB Output is correct
7 Correct 501 ms 104292 KB Output is correct
8 Correct 579 ms 104160 KB Output is correct
9 Correct 459 ms 102040 KB Output is correct
10 Correct 470 ms 102004 KB Output is correct
11 Correct 425 ms 102084 KB Output is correct
12 Correct 538 ms 102060 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1670 ms 293952 KB Output is correct
2 Correct 1518 ms 293960 KB Output is correct
3 Correct 1120 ms 185472 KB Output is correct
4 Correct 1214 ms 185576 KB Output is correct
5 Correct 1090 ms 185612 KB Output is correct
6 Correct 1365 ms 208116 KB Output is correct
7 Correct 1351 ms 208164 KB Output is correct
8 Correct 1350 ms 208396 KB Output is correct
9 Correct 1218 ms 204028 KB Output is correct
10 Correct 1171 ms 203900 KB Output is correct
11 Correct 1162 ms 203924 KB Output is correct
12 Correct 1238 ms 204132 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1737 ms 301960 KB Output is correct
2 Correct 1741 ms 301428 KB Output is correct
3 Correct 1498 ms 190800 KB Output is correct
4 Correct 1589 ms 193540 KB Output is correct
5 Correct 1314 ms 190008 KB Output is correct
6 Correct 1646 ms 216348 KB Output is correct
7 Correct 1728 ms 213036 KB Output is correct
8 Correct 1638 ms 215064 KB Output is correct
9 Correct 1316 ms 210496 KB Output is correct
10 Correct 1298 ms 210172 KB Output is correct
11 Correct 1397 ms 210176 KB Output is correct
12 Correct 1349 ms 211476 KB Output is correct