oj.uz

Submission #865799

# Submission time Handle Problem Language Result Execution time Memory
865799 2023-10-24T16:36:09 Z mychecksedad Prize (CEOI22_prize) C++17
100 / 100
 2245 ms 460724 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22, MX = 30;

vector<array<int, 2>> Q;
void ask(int i, int j){
  cout << "? " << i << ' ' << j << '\n';
  Q.pb({i, j});
}

int n, k, q, t, root[2], par[N][2], dep[N][2], dp[N][K][2], up[N][K][2], tin[N][2], tout[N][2], timer = 0, pref[N][2];
vector<int> g[N][2], comp, r[N];
vector<array<int, 2>> E[N][2];
vector<array<bool, 2>> vis(N);

void dfs(int v, int d, int rep){
  if(comp.size() < k){
    comp.pb(v);
  }
  tin[v][rep] = timer++;
  dep[v][rep] = d;
  for(int u: g[v][rep]) dfs(u, d+1, rep);
  tout[v][rep] = timer++;
}

bool is_parent(int u, int v, int rep){
  return tin[u][rep] <= tin[v][rep] && tout[v][rep] <= tout[u][rep];
}

int _lca(int u, int v, int rep){
  if(is_parent(u, v, rep)) return u;
  if(is_parent(v, u, rep)) return v;
  for(int j = K - 1; j >= 0; --j)
    if(!is_parent(up[u][j][rep], v, rep)) u = up[u][j][rep];
  return up[u][0][rep];
}

void full_ask(){
  cout << "!" << endl;
  for(auto f: Q){
    int x, y, z, w; cin >> x >> y >> z >> w;
    int lca1 = _lca(f[0], f[1], 0);
    int lca2 = _lca(f[0], f[1], 1);
    // cout << f[0] << ' ' << f[1] << ' ' << lca1 << ' ' << lca2 << endl;
    comp.pb(lca2);
    E[lca1][0].pb({f[0], x});
    E[f[0]][0].pb({lca1, -x});
    E[lca1][0].pb({f[1], y});
    E[f[1]][0].pb({lca1, -y});
    E[lca2][1].pb({f[0], z});
    E[f[0]][1].pb({lca2, -z});
    E[lca2][1].pb({f[1], w});
    E[f[1]][1].pb({lca2, -w});
  }
}

void calc(int v, int rep){
  vis[v][rep] = 1;
  for(auto U: E[v][rep]){
    int u = U[0], w = U[1];
    if(!vis[u][rep]){
      pref[u][rep] = pref[v][rep] + w;
      calc(u, rep);
    }
  }
}

void solve(){
  cin >> n >> k >> q >> t;
  for(int rep = 0 ; rep < 2; ++rep){
    for(int i = 1; i <= n; ++i){
      int p; cin >> p;
      up[i][0][rep] = p;
      if(p != -1) g[p][rep].pb(i);
      else root[rep] = i;
    }
  }
  timer = 0;
  dfs(root[0], 0, 0);
  timer = 0;
  dfs(root[1], 0, 1);
  // cout << comp.size() << '\n';
  for(int v: comp) cout << v << ' ';
  cout << endl;

  sort(all(comp), [&](const int &x, const int&y){
    return tin[x][1] < tin[y][1];
  });
  
  for(int i = 0; i < k - 1; ++i) ask(comp[i], comp[i + 1]);


  for(int rep = 0; rep < 2; ++rep){
    up[root[rep]][0][rep] = root[rep];
    for(int j = 1; j < K; ++j){
      for(int i = 1; i <= n; ++i){
        up[i][j][rep] = up[up[i][j - 1][rep]][j - 1][rep];
      }
    }
  }

  vis.resize(n+1);
  full_ask();
  for(int i = 1; i <= n; ++i) pref[i][0] = pref[i][1] = 0; 
  calc(root[0], 0);
  calc(root[1], 1);
  for(int v: comp){
    if(!vis[v][0]) calc(v, 0);
    if(!vis[v][1]) calc(v, 1);
  }

  vector<array<int, 2>> qq;
  for(;t--;){
    int u, v; cin >> u >> v;
    qq.pb({u, v});
  }
  for(auto [u, v]: qq){
    for(int rep = 0; rep < 2; ++rep){
      int lca = _lca(u, v, rep);
      cout << pref[v][rep] + pref[u][rep] - 2 * pref[lca][rep] << ' ';
    }
    en;
  }
  cout << endl;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  // cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:24:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |   if(comp.size() < k){
      |      ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:137:15: warning: unused variable 'aa' [-Wunused-variable]
  137 |   int tt = 1, aa;
      |               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 294360 KB Output is correct
2 Correct 1056 ms 297352 KB Output is correct
3 Correct 819 ms 249432 KB Output is correct
4 Correct 784 ms 248400 KB Output is correct
5 Correct 787 ms 251892 KB Output is correct
6 Correct 1031 ms 260388 KB Output is correct
7 Correct 1006 ms 259908 KB Output is correct
8 Correct 1033 ms 259568 KB Output is correct
9 Correct 826 ms 248564 KB Output is correct
10 Correct 845 ms 254544 KB Output is correct
11 Correct 707 ms 257104 KB Output is correct
12 Correct 721 ms 259892 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 307324 KB Output is correct
2 Correct 862 ms 302744 KB Output is correct
3 Correct 733 ms 258676 KB Output is correct
4 Correct 821 ms 261336 KB Output is correct
5 Correct 765 ms 260368 KB Output is correct
6 Correct 1253 ms 267264 KB Output is correct
7 Correct 1195 ms 270784 KB Output is correct
8 Correct 1205 ms 271032 KB Output is correct
9 Correct 1024 ms 269512 KB Output is correct
10 Correct 1033 ms 269900 KB Output is correct
11 Correct 1002 ms 266008 KB Output is correct
12 Correct 1141 ms 269688 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 296384 KB Output is correct
2 Correct 804 ms 296048 KB Output is correct
3 Correct 563 ms 249560 KB Output is correct
4 Correct 563 ms 249692 KB Output is correct
5 Correct 580 ms 249564 KB Output is correct
6 Correct 748 ms 259368 KB Output is correct
7 Correct 694 ms 259492 KB Output is correct
8 Correct 673 ms 260012 KB Output is correct
9 Correct 599 ms 257516 KB Output is correct
10 Correct 607 ms 257972 KB Output is correct
11 Correct 618 ms 257908 KB Output is correct
12 Correct 603 ms 257296 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1889 ms 450892 KB Output is correct
2 Correct 1783 ms 450500 KB Output is correct
3 Correct 1253 ms 357468 KB Output is correct
4 Correct 1252 ms 357652 KB Output is correct
5 Correct 1224 ms 357504 KB Output is correct
6 Correct 1781 ms 377584 KB Output is correct
7 Correct 1735 ms 377624 KB Output is correct
8 Correct 1756 ms 377072 KB Output is correct
9 Correct 1560 ms 373196 KB Output is correct
10 Correct 1554 ms 372968 KB Output is correct
11 Correct 1552 ms 373332 KB Output is correct
12 Correct 1598 ms 373400 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1856 ms 460724 KB Output is correct
2 Correct 1900 ms 460520 KB Output is correct
3 Correct 1379 ms 365232 KB Output is correct
4 Correct 1466 ms 369316 KB Output is correct
5 Correct 1340 ms 364112 KB Output is correct
6 Correct 2245 ms 389020 KB Output is correct
7 Correct 2115 ms 384456 KB Output is correct
8 Correct 2152 ms 387196 KB Output is correct
9 Correct 1797 ms 382420 KB Output is correct
10 Correct 1762 ms 381372 KB Output is correct
11 Correct 1768 ms 381232 KB Output is correct
12 Correct 1824 ms 383608 KB Output is correct