Submission #805482

#	Time	Username	Problem	Language	Result	Execution time	Memory
805482		rnl42	Prize (CEOI22_prize)	C++14	100 / 100	1741 ms	301960 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24