Submission #1304394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304394		loom	Prize (CEOI22_prize)	C++20	54 / 100	1601 ms	180780 KiB

Main

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

const int N = 5e5+1;
vector<int> g[2][N], vc, sub;
vector<pair<int,int>> g2[2][N];
int dep[2][N], dis[2][N], vis[2][N], tin[N], up[2][N][20];
int n, k, q, t, w, c;

void dfs(int v){
   vc.clear();
   vc.push_back(v);

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

      if(!w and sub.size() < k) sub.push_back(v);
      if(w) tin[v] = c++;

      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){
   vc.clear();
   vc.push_back(v);
   vis[w][v] = 1;

   while(!vc.empty()){
      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 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(){
   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 j : {0, 1}){
      w = j;
      up[j][r[j]][0] = r[j];
      dfs(r[j]);

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

   sort(sub.begin(), sub.end(), [&](int x, int y){
      return tin[x] < tin[y];
   });

   for(int x : sub) cout<<x<<" ";
   cout<<nl;

   for(int i = 1; i < k; i++) cout<<"?" _ sub[i-1] _ sub[i]<<nl;
   cout<<'!'<<nl;

   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];

      int x = sub[i-1], y = sub[i];

      for(int j : {0, 1}){
         w = j;
         int l = lca(x, y);

         add(l, x, d1[j]);
         add(l, y, d2[j]);
      }
   }

   r[1] = lca(sub[0], sub[k-1]);

   for(int j : {0, 1}){
      w = j;
      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<<(long long) 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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24