oj.uz

답안 #844439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
844439 2023-09-05T13:12:29 Z vjudge1 Klasika (COCI20_klasika) C++17
110 / 110
 1919 ms 276756 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 = 18, KK = 30;


struct Query{
  int a, b, t, idx;
};

struct Node{
  Node *l, *r;
  int min_time;
  bool is;
  Node(){
    l = r = nullptr;
    min_time = MOD;
    is = 0;
  }
  void extend(){
    if(l == nullptr){
      l = new Node();
    }
    if(r == nullptr){
      r = new Node();
    }
  }
  void update(int new_time, int x, int dep){
    min_time = min(min_time, new_time);
    is = 1;
    if(dep == -1) return;
    extend();
    if(x&(1<<dep)){
      r->update(new_time, x, dep - 1);
    }else{
      l->update(new_time, x, dep - 1);
    }
  }
  int get(int val, int dep, int qt){
    extend();
    // cout << dep << ' ' << val << ' ' << min_time << ' ' << is << '\n';
    if((1<<dep)&val){
      if(l->is && l->min_time <= qt){
        return (1<<dep) + l->get(val, dep - 1, qt);
      }
      if(r->is && r->min_time <= qt)
        return r->get(val, dep - 1, qt);
      return 0;
    }
    if(r->is && r->min_time <= qt){
      return (1<<dep) + r->get(val, dep - 1, qt);
    }
    if(l->is && l->min_time <= qt)
      return l->get(val, dep - 1, qt);
    return 0;
  }
  void freeall(){
    if(l != nullptr){
      l->freeall();
    }
    if(r != nullptr){
      r->freeall();
    } 
    free(l);
    free(r);
  }
};

int q, ans[N], sz[N], n = 1, pref[N], bigxo[N];
vector<array<int, 3>> g[N];
vector<Query> Q[N];
vector<Node*> trie;
vector<pair<int, int>> values[N];

void pre(int v){
  sz[v] = 1;
  for(auto U: g[v]){
    int u = U[0];
    pref[u] = pref[v] ^ U[1];
    pre(u);
    sz[v] += sz[u];
  }
}

int calcc(int a, int b){
  return pref[a]^pref[b];
}
void dfs(int v, int w, int tm){
  int big = -1;
  for(auto U: g[v]){
    int u = U[0];
    dfs(u, U[1], U[2]);
    if(big == -1 || sz[u] > sz[big]) big = u;
  }
  if(big != -1){
    swap(trie[v], trie[big]);
    values[v].swap(values[big]);
  }else{
    trie[v] = new Node();
    trie[v]->is = 1;
  }
  for(auto U: g[v]){
    if(U[0] != big){
      for(auto x: values[U[0]]){
        trie[v]->update(x.second, x.first, KK);
        values[v].pb({x.first, x.second});
        // cout << (x.first ^ U[1] ^ bigxo[v]) << ' ' << v << '\n';
      }
      trie[U[0]]->freeall();
    }
  }
  // for(auto f: values[v]){
    // cout << f.first << ' ' << f.second << ' ' << v << '\n';
  // }
  values[v].pb({pref[v], tm});
  trie[v]->update(tm, pref[v], KK);
  for(auto qq: Q[v]){
    int xo = pref[qq.a];
    ans[qq.idx] = trie[v]->get(xo, KK, qq.t);
    // cout <<qq.t << ' ';
  }
  /*
  values[v].pb({w, tm});
  // cout << w << ' ' << tm << '\n';
  trie[v]->update(tm, w, KK);
  */
}

void solve(){
  cin >> q;
  int qq = 0;
  for(int i = 1; i <= q; ++i){
    string s; cin >> s;
    if(s == "Add"){
      int p, w; cin >> p >> w;
      g[p].pb({++n, w, i});
    }else{
      int a, b; cin >> a >> b;
      Q[b].pb({a, b, i, ++qq});
    }
  }
  pref[1] = 0;
  pre(1);
  trie.resize(n+1);
  dfs(1, 0, 0);

  for(int i = 1; i <= qq; ++i) cout << ans[i] << '\n';
}


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

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:159:15: warning: unused variable 'aa' [-Wunused-variable]
  159 |   int tt = 1, aa;
      |               ^~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 17 ms 78680 KB Output is correct
3 Correct 17 ms 78680 KB Output is correct
4 Correct 20 ms 78680 KB Output is correct
5 Correct 19 ms 78684 KB Output is correct
6 Correct 17 ms 78680 KB Output is correct
7 Correct 18 ms 78680 KB Output is correct
8 Correct 20 ms 78684 KB Output is correct
9 Correct 17 ms 78680 KB Output is correct
10 Correct 20 ms 78680 KB Output is correct
11 Correct 20 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 17 ms 78680 KB Output is correct
3 Correct 17 ms 78680 KB Output is correct
4 Correct 20 ms 78680 KB Output is correct
5 Correct 19 ms 78684 KB Output is correct
6 Correct 17 ms 78680 KB Output is correct
7 Correct 18 ms 78680 KB Output is correct
8 Correct 20 ms 78684 KB Output is correct
9 Correct 17 ms 78680 KB Output is correct
10 Correct 20 ms 78680 KB Output is correct
11 Correct 20 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct
13 Correct 18 ms 79196 KB Output is correct
14 Correct 22 ms 79708 KB Output is correct
15 Correct 22 ms 80472 KB Output is correct
16 Correct 22 ms 80728 KB Output is correct
17 Correct 21 ms 79196 KB Output is correct
18 Correct 24 ms 79756 KB Output is correct
19 Correct 24 ms 80656 KB Output is correct
20 Correct 29 ms 81224 KB Output is correct
21 Correct 22 ms 79196 KB Output is correct
22 Correct 22 ms 79816 KB Output is correct
23 Correct 26 ms 80216 KB Output is correct
24 Correct 23 ms 80696 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 133088 KB Output is correct
2 Correct 269 ms 172956 KB Output is correct
3 Correct 295 ms 210368 KB Output is correct
4 Correct 334 ms 246772 KB Output is correct
5 Correct 618 ms 132608 KB Output is correct
6 Correct 985 ms 185912 KB Output is correct
7 Correct 1447 ms 220252 KB Output is correct
8 Correct 1885 ms 257092 KB Output is correct
9 Correct 332 ms 126812 KB Output is correct
10 Correct 482 ms 163388 KB Output is correct
11 Correct 586 ms 196540 KB Output is correct
12 Correct 664 ms 227716 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 17 ms 78680 KB Output is correct
3 Correct 17 ms 78680 KB Output is correct
4 Correct 20 ms 78680 KB Output is correct
5 Correct 19 ms 78684 KB Output is correct
6 Correct 17 ms 78680 KB Output is correct
7 Correct 18 ms 78680 KB Output is correct
8 Correct 20 ms 78684 KB Output is correct
9 Correct 17 ms 78680 KB Output is correct
10 Correct 20 ms 78680 KB Output is correct
11 Correct 20 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct
13 Correct 18 ms 79196 KB Output is correct
14 Correct 22 ms 79708 KB Output is correct
15 Correct 22 ms 80472 KB Output is correct
16 Correct 22 ms 80728 KB Output is correct
17 Correct 21 ms 79196 KB Output is correct
18 Correct 24 ms 79756 KB Output is correct
19 Correct 24 ms 80656 KB Output is correct
20 Correct 29 ms 81224 KB Output is correct
21 Correct 22 ms 79196 KB Output is correct
22 Correct 22 ms 79816 KB Output is correct
23 Correct 26 ms 80216 KB Output is correct
24 Correct 23 ms 80696 KB Output is correct
25 Correct 235 ms 133088 KB Output is correct
26 Correct 269 ms 172956 KB Output is correct
27 Correct 295 ms 210368 KB Output is correct
28 Correct 334 ms 246772 KB Output is correct
29 Correct 618 ms 132608 KB Output is correct
30 Correct 985 ms 185912 KB Output is correct
31 Correct 1447 ms 220252 KB Output is correct
32 Correct 1885 ms 257092 KB Output is correct
33 Correct 332 ms 126812 KB Output is correct
34 Correct 482 ms 163388 KB Output is correct
35 Correct 586 ms 196540 KB Output is correct
36 Correct 664 ms 227716 KB Output is correct
37 Correct 222 ms 134100 KB Output is correct
38 Correct 319 ms 174620 KB Output is correct
39 Correct 312 ms 212856 KB Output is correct
40 Correct 335 ms 247936 KB Output is correct
41 Correct 496 ms 141460 KB Output is correct
42 Correct 948 ms 188032 KB Output is correct
43 Correct 1285 ms 213568 KB Output is correct
44 Correct 1919 ms 276756 KB Output is correct
45 Correct 274 ms 127688 KB Output is correct
46 Correct 416 ms 162988 KB Output is correct
47 Correct 547 ms 195456 KB Output is correct
48 Correct 652 ms 227156 KB Output is correct