제출 #500244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500244		Mounir	Klasika (COCI20_klasika)	C++14	33 / 110	1174 ms	524292 KiB

klasika

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define x first
#define y second
//#define int long long
using namespace std;

const int OO = 1e9, N = 3e5, T = 30;
bitset<T> AXOR = (1 << 30) - 1;

//Plus petit dans le plus grand

struct Trie {
      vector<vector<int>> arbre;
      vector<int> dateMin, dateDico;
      vector<bitset<T>> dico;

      void init(){
            for (int i = 0; i < 2; ++i){
                  arbre.pb({0, 0});
                  dateMin.pb(OO);
            }
      }

      void ajouter(bitset<30> line, int dateAjout){
       //     cout << "ajouter " << line << " " << dateAjout << endl;
            dico.pb(line);
            string str  = line.to_string();
            reverse(all(str));
            line = (bitset<T>)str;

            dateDico.pb(dateAjout);
            int noeud = 1;
            for (int i = 0; i < T; ++i){
                  int cara = line[i];
               //   cout << noeud << " " << cara << endl;
                  if (arbre[noeud][cara] == 0){
                        arbre[noeud][cara] = sz(arbre);
                        arbre.pb({0, 0});
                        dateMin.pb(OO);
                  }

                  noeud = arbre[noeud][cara];
                  chmin(dateMin[noeud], dateAjout);
            }
      }

      bitset<T> search(bitset<30> cible, int borneSup){
        /*    string str  = cible.to_string();
            reverse(all(str));
            cible = (bitset<T>)str;
*/
            int noeud = 1;
            bitset<T> retour;
         //   cout << "recherche " << (cible^AXOR).to_ulong() << endl;
            for (int i = 0; i < T; ++i){
                  int cara = cible[i];
                  if (arbre[noeud][cara] != 0 && dateMin[arbre[noeud][cara]] <= borneSup){
                        noeud = arbre[noeud][cara];
                        retour[i] = cara;
                  }
                  else {
                        noeud = arbre[noeud][1 - cara];
                        retour[i] = 1 - cara;
                  }
           //       cout << retour[i];
            }
         //   cout << endl;
            return retour;
      }

      void fusionner(Trie autre){
            for (int i = 0; i < sz(autre.dico); ++i)
                  ajouter(autre.dico[i], autre.dateDico[i]);
      }
};

vector<Trie> parcours;
int fusion(int pere, int fils){
      if (sz(parcours[pere].dico) < sz(parcours[fils].dico))
            return fusion(fils, pere);
      parcours[pere].fusionner(parcours[fils]);
      return pere;
}

vector<int> enfants[N];
int dateAjout[N];
bitset<T> xorPref[N];

struct Req {
      int iReq;
      bitset<T> cste;
};

vector<Req> reqs[N];
bitset<T> ans[N];
vector<bitset<T>> poids[N];

void calcPref(int noeud, bitset<T> cur){
    //  cout << "calc pref" << noeud << " " << cur << endl;
      xorPref[noeud] = cur;
      for (int i = 0; i < sz(enfants[noeud]); ++i)
            calcPref(enfants[noeud][i], cur^poids[noeud][i]);
}

int dfs(int noeud){
     // cout << "dfs " << noeud << endl;
      int id = sz(parcours);
      parcours.pb({});
      parcours[id].init();
      for (int enfant : enfants[noeud])
            id = fusion(id, dfs(enfant));
      //cout << "ppf" << noeud << endl;
      parcours[id].ajouter(xorPref[noeud], dateAjout[noeud]);
     // cout << "pf " << noeud << endl;

      for (Req req : reqs[noeud]){
            ans[req.iReq] = req.cste^parcours[id].search(AXOR^req.cste, req.iReq);
            string str  = ans[req.iReq].to_string();
            reverse(all(str));
            ans[req.iReq] = (bitset<T>)str;
      }
      return id;
}


bool estReq[N];
int deb[N], daron[N];

signed main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);

      int nReqs; cin >> nReqs;
      int nNoeuds = 2;
      for (int iReq = 0; iReq < nReqs; ++iReq){
            string nature;
            int x, y; cin >> nature >> x >> y;
            
            if (nature == "Add"){
                  dateAjout[nNoeuds] = iReq;
                  enfants[x].pb(nNoeuds++);
                  poids[x].pb(y);
            }
            else {
                  estReq[iReq] = true;
                  deb[iReq] = x;
                  daron[iReq] = y;
            }
      }

      //cout << "bonsoir" << endl;
    //  cout << AXOR << endl;

      calcPref(1, 0);
      for (int iReq = 0; iReq < nReqs; ++iReq){
            if (!estReq[iReq]) continue;
            bitset<T> cste = xorPref[deb[iReq]];
            string str  = cste.to_string();
            reverse(all(str));
            cste = (bitset<T>)str;
            reqs[daron[iReq]].pb({iReq, cste});
      }

     // cout << "salut" << endl;

      dfs(1);
   //   for (int noeud = 1; noeud <= nNoeuds; ++noeud)
     //       cout << "xor " << noeud << " : " << xorPref[noeud] << endl;

      for (int iReq = 0; iReq < nReqs; ++iReq){
            if (estReq[iReq])
                  cout << ans[iReq].to_ulong() << endl;
      }
      return 0;   
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44