Submission #1304272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304272		loom	Prize (CEOI22_prize)	C++20	0 / 100	1399 ms	244872 KiB

Main

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

const int N = 5e5+1;
vector<int> g[2][N];
vector<pair<int,int>> g2[2][N];
int dep[2][N], dis[2][N], vis[2][N], up[2][N][20];
int w = 0;

void dfs(int v){
   vector<int> vc;
   vc.push_back(v);

   while(!vc.empty()){
      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 v){
   vector<int> vc;
   vc.push_back(v);

   while(!vc.empty()){
      v = vc.back();
      vc.pop_back();
      vis[w][v] = 1;

      for(auto [ch, d] : g2[w][v]){
         if(vis[w][ch]) continue;
         
         dis[w][ch] = dis[w][v] + d;
         vc.push_back(ch);
      }
   }
}  

int lca(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 < 20; i++) if(k & 1<<i) y = up[w][y][i];

   if(x == y) return x;

   for(int i = 19; 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);
      }
   }

   for(int i = 1; i <= k; i++) cout<<i<<" ";
   cout<<nl;

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

   for(int j : {0, 1}){
      w = j;
      up[j][r[j]][0] = r[j];
      dfs(r[j]);

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

   auto add = [&](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}){
         w = j;
         int l = lca(i, i+1);

         add(l, i, d1[j]);
         add(l, i+1, d2[j]);
      }
   }

   for(int j : {0, 1}){
      w = j;
      r[j] = 1;

      for(int i = 2; i <= k; i++){
         r[j] = lca(r[j], i);
      }
   }

   for(int j : {0, 1}){
      w = j;
      dis[j][r[j]] = 0;
      dfs2(r[j]);
   }

   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}){
         w = j;

         cout<<dis[w][x] + dis[w][y] - 2 * dis[w][lca(x, y)]<<" ";
      }
      cout<<nl;
   }
}  

signed main(){
   int t = 1;
   //cin>>t;
   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