Submission #952648

#	Time	Username	Problem	Language	Result	Execution time	Memory
952648		Vladth11	Prize (CEOI22_prize)	C++14	100 / 100	3399 ms	395836 KiB

Main

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 1000001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int n;

class Tree{
public:
    vector <int> v[NMAX];
    int dp[nrbits + 1][NMAX];
    vector <int> preorder;
    pii timp[NMAX];
    int stamp, root;
    void init(){
        preorder.clear();
        stamp = root = 0;
        for(int i = 0; i <= n; i++){
            v[i].clear();
            timp[i].first = timp[i].second = 0;
        }
        for(int j = 0; j <= nrbits; j++){
            for(int i = 0; i <= n; i++)
                dp[j][i] = 0;
        }
    }
    bool isParent(int a, int b){
        return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
    }
    int LCA(int a, int b){
        int r = a, pas = nrbits;
        while(pas >= 0){
            int nxt = dp[pas][r];
            if(nxt != 0 && !isParent(nxt, b)){
                r = nxt;
            }
            pas--;
        }
        if(!isParent(r, b))
            r = dp[0][r];
        return r;
    }
    void setFather(int a, int b){
        if(a == -1){
            root = b;
            return;
        }
        v[b].push_back(a);
        v[a].push_back(b);
    }
    void DFS(int node, int p){
        preorder.push_back(node);
        timp[node].first = ++stamp;
        dp[0][node] = p;
        for(auto x : v[node]){
            if(x == p) continue;
            DFS(x, node);
        }
        timp[node].second = stamp;
    }
    void prec(){
        for(int j = 1; j <= nrbits; j++){
            for(int i = 1; i <= n; i++){
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }
        }
    }
}arb1, arb2;

class DSU{ /// Momentan DSU doar cu numele
public:
   vector <pii> v[NMAX];
   int dist[NMAX];
    void init(){
        for(int i = 1; i <= n; i++){
            v[i].clear();
            dist[i] = 2e9;
        }
    }
    void setDistance(int a, int b, int c){
        v[a].push_back({b, c});
        v[b].push_back({a, -c});
    }
    void DFS(int node){
        for(auto x : v[node]){
            if(dist[x.first] == 2e9){
                dist[x.first] = x.second + dist[node];
                DFS(x.first);
            }
        }
    }
    void baga(int x){
        dist[x] = 0;
        DFS(x);
    }
}dsu1, dsu2;

pii sol[NMAX];

bool cmp(int a, int b){
    return arb2.timp[a].first < arb2.timp[b].first;
}

signed main() {
#ifdef HOME
  //  ifstream cin(".in");
   // ofstream cout(".out");
#endif // HOME
    int k, q, t, rt1 = 0, rt2 = 0;
    cin >> n >> k >> q >> t;
    arb1.init();
    arb2.init();
    dsu1.init();
    dsu2.init();
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        arb1.setFather(p, i);
    }
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        arb2.setFather(p, i);
    }
    arb1.DFS(arb1.root, 0);
    arb2.DFS(arb2.root, 0);
    arb1.prec();
    arb2.prec();

    vector <int> chosen;
    for(int i = 0; i < k; i++){
        chosen.push_back(arb1.preorder[i]);
    }
    for(auto x : chosen){
        cout << x << " ";
    }
    cout << "\n";
    sort(chosen.begin(), chosen.end(), cmp);
    for(int i = 0; i < chosen.size() - 1; i++){
        cout << "? " << chosen[i] << " " << chosen[i + 1] << "\n";
    }
    cout << "!" << endl;
    int minim = 2e9;
    int cine = 0;
    for(int i = 0; i < chosen.size() - 1; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int lca1 = arb1.LCA(chosen[i], chosen[i + 1]);
        int lca2 = arb2.LCA(chosen[i], chosen[i + 1]);
        if(arb2.timp[lca2].first < minim){
            minim = arb2.timp[lca2].first;
            cine = lca2;
        }
        dsu1.setDistance(lca1, chosen[i], a);
        dsu1.setDistance(lca1, chosen[i + 1], b);
        dsu2.setDistance(lca2, chosen[i], c);
        dsu2.setDistance(lca2, chosen[i + 1], d);
    }
    dsu1.baga(arb1.root);
    dsu2.baga(cine);
    for(int i = 0; i < t; i++){
        int a, b;
        cin >> a >> b;
        int lca1 = arb1.LCA(a, b);
        int lca2 = arb2.LCA(a, b);
        sol[i] = {dsu1.dist[a] - 2 * dsu1.dist[lca1] + dsu1.dist[b], dsu2.dist[a] - 2 * dsu2.dist[lca2] + dsu2.dist[b]};
    }
    for(int i = 0; i < t; i++){
        cout << sol[i].first << " " << sol[i].second << "\n";
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:120:18: warning: unused variable 'rt1' [-Wunused-variable]
  120 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                  ^~~
Main.cpp:120:27: warning: unused variable 'rt2' [-Wunused-variable]
  120 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                           ^~~

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