Submission #1304321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304321		loom	Prize (CEOI22_prize)	C++20	0 / 100	1207 ms	149760 KiB

Main

// Just to check if code given by ChatGPT actually works lol

#include<bits/stdc++.h>
using namespace std;
#define inf (int)2e9
#define _ <<' '<<
#define nl endl

const int N = 5e5+1;
const int LOG = 19;

vector<int> g[2][N];
vector<pair<int,int>> g2[2][N];
int dep[2][N], dis[2][N], vis[2][N];
int up[2][N][LOG];

void dfs(int w, int root){
   vector<int> vc;
   vc.push_back(root);

   while(!vc.empty()){
      int v = vc.back();
      vc.pop_back();

      for(int ch : g[w][v]){
         dep[w][ch] = dep[w][v] + 1;
         up[w][ch][0] = v;
         vc.push_back(ch);
      }
   }
}

void dfs2(int w, int root){
   vector<int> vc;
   vc.push_back(root);
   vis[w][root] = 1;

   while(!vc.empty()){
      int v = vc.back();
      vc.pop_back();
      
      for(auto [ch, d] : g2[w][v]){
         if(vis[w][ch]) continue;
         vis[w][ch] = 1;
         
         dis[w][ch] = dis[w][v] + d;
         vc.push_back(ch);
      }
   }
}  

int lca(int w, int x, int y){
   if(dep[w][x] > dep[w][y]) swap(x, y);

   int k = dep[w][y] - dep[w][x];
   for(int i = 0; i < LOG; i++) if(k & 1<<i) y = up[w][y][i];

   if(x == y) return x;

   for(int i = LOG-1; i >= 0; i--){
      if(up[w][x][i] != up[w][y][i]){
         x = up[w][x][i];
         y = up[w][y][i];
      }
   }

   return up[w][x][0];
}

void solve(){
   int n, k, q, t;
   cin>>n>>k>>q>>t;

   int r[2];
   for(int j : {0, 1}){
      for(int i = 1; i <= n; i++){
         int p;
         cin>>p;

         if(p == -1) r[j] = i;
         else g[j][p].push_back(i);
      }
   }

   // Output chosen subset (first K nodes)
   for(int i = 1; i <= k; i++) cout<<i<<" ";
   cout<<nl;

   // Ask queries for consecutive pairs
   for(int i = 1; i < k; i++){
      cout<<"?" _ i _ i+1<<nl;
   }
   cout<<'!'<<nl;

   // Build binary lifting tables for both trees
   for(int j : {0, 1}){
      up[j][r[j]][0] = r[j];
      dfs(j, r[j]);

      for(int l = 1; l < LOG; l++){
         for(int i = 1; i <= n; i++){
            up[j][i][l] = up[j][up[j][i][l-1]][l-1];
         }
      }
   }

   // Process answers and build equation graphs
   auto add = [&](int w, int x, int y, int d){
      g2[w][x].push_back({y, d});
      g2[w][y].push_back({x, -d});
   };

   for(int i = 1; i < k; i++){
      int d1[2], d2[2];
      cin>>d1[0]>>d2[0]>>d1[1]>>d2[1];

      for(int j : {0, 1}){
         int l = lca(j, i, i+1);
         add(j, l, i, d1[j]);
         add(j, l, i+1, d2[j]);
      }
   }

   // Find roots (LCA of all chosen nodes) for each tree
   int root[2];
   for(int j : {0, 1}){
      root[j] = 1;
      for(int i = 2; i <= k; i++){
         root[j] = lca(j, root[j], i);
      }
   }

   // Compute distances from roots using DFS
   for(int j : {0, 1}){
      dis[j][root[j]] = 0;
      dfs2(j, root[j]);
   }

   // Answer host's questions
   vector<pair<int,int>> qry;
   for(int i = 0; i < t; i++){
      int x, y;
      cin>>x>>y;
      qry.push_back({x, y});
   }

   for(auto [x, y] : qry){
      for(int j : {0, 1}){
         int l = lca(j, x, y);
         cout<< dis[j][x] + dis[j][y] - 2 * dis[j][l] <<" ";
      }
      cout<<nl;
   }
}  

signed main(){
   int t = 1;
   while(t--) solve();
   return 0;
}

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