oj.uz

Submission #865616

# Submission time Handle Problem Language Result Execution time Memory
865616 2023-10-24T12:30:33 Z mychecksedad Prize (CEOI22_prize) C++17
10 / 100
 640 ms 302036 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, 3>> Q;
void ask(int i, int j){
  cout << "? " << i << ' ' << j << '\n';
  Q.pb({i, j, 0});
}

int n, k, q, t, root1, root2, w[N], par[N], dep[N], dp[N][K], up[N][K], tin[N], tout[N], timer = 0;
vector<int> g[N], r[N], comp;

void full_ask(){
  cout << "!" << endl;
  for(auto f: Q){
    int x, y, z, w; cin >> x >> y >> z >> w;
    dp[f[0]][0] = x;
  }
}

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

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

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

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

  up[root1][0] = root1;
  for(int j = 1; j < K; ++j){
    for(int v: comp){
      up[v][j] = up[up[v][j - 1]][j - 1];
      dp[v][j] = dp[v][j - 1] + dp[up[v][j - 1]][j - 1];
    }
  }
  vector<array<int, 2>> qq;
  for(;t--;){
    int u, v; cin >> u >> v;
    qq.pb({u, v});
  }
  for(auto [u, v]: qq){
    int ans = 0, lca = _lca(u, v);
    for(int j = K - 1; j >= 0; --j){
      if((dep[u]-dep[lca])&(1<<j)) ans += dp[u][j], u = up[u][j];
      if((dep[v]-dep[lca])&(1<<j)) ans += dp[v][j], v = up[v][j];
    }
    cout << ans << ' ' << ans << '\n';
  }
  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)':
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   if(comp.size() < k){
      |      ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:102:15: warning: unused variable 'aa' [-Wunused-variable]
  102 |   int tt = 1, aa;
      |               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 185496 KB Output is correct
2 Correct 479 ms 188468 KB Output is correct
3 Correct 342 ms 168588 KB Output is correct
4 Correct 379 ms 167824 KB Output is correct
5 Correct 379 ms 168484 KB Output is correct
6 Correct 494 ms 174144 KB Output is correct
7 Correct 478 ms 174076 KB Output is correct
8 Correct 515 ms 174228 KB Output is correct
9 Correct 362 ms 168092 KB Output is correct
10 Correct 369 ms 168236 KB Output is correct
11 Correct 344 ms 167924 KB Output is correct
12 Correct 377 ms 168560 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 280 ms 187120 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 180424 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 382 ms 263164 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 640 ms 302036 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -