Submission #334968

#	Time	Username	Problem	Language	Result	Execution time	Memory
334968		Dymo	Klasika (COCI20_klasika)	C++14	33 / 110	1420 ms	524292 KiB

klasika

#include<bits/stdc++.h>
using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e5+100001;
const ll mod =1e9+7 ;
const ll base=maxn*2;
pll a[maxn];
bool t[maxn];
vector<pll> adj[maxn];
ll val[maxn];
ll f[maxn];
ll l[maxn];
ll cnt=0;
void dfs(ll u)
{
    cnt++;
    f[u]=cnt;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll cst=p.ss;
        val[to]=val[u]^cst;
        dfs(to);
    }
    l[u]=cnt;
}
struct tk
{
    vector<pll> nxt;
    ll cntnw=1;
    void add(ll x)
    {
        ll nw=1;
        if (nxt.size()==0)
        {
            nxt.emplace_back();
            nxt.emplace_back();

        }
        for (int i=30;i>=0;i--)
        {
            if (x&(1ll<<i))
            {
                 if (nxt[nw].ff==0)
                 {

                     cntnw++;
                     nxt[nw].ff=cntnw;
                     nxt.emplace_back();
                 }
                 nw=nxt[nw].ff;
            }
            else
            {
                  if (nxt[nw].ss==0)
                 {
                     cntnw++;
                     nxt[nw].ss=cntnw;
                     nxt.emplace_back();
                 }
                 nw=nxt[nw].ss;
            }
           // cout <<"WTF"<<endl;
        }
    }
    ll que(ll x)
    {
        if (nxt.size()<=2)
        {
            return 0;
        }
        ll nw=1;
        ll ans=0;
        for (int i=30;i>=0;i--)
        {
            if (x&(1ll<<i))
            {
                if (nxt[nw].ss)
                {
                    ans+=(1ll<<i);
                    nw=nxt[nw].ss;
                }
                else
                {
                    nw=nxt[nw].ff;
                }
            }
            else
            {
                if (nxt[nw].ff)
                {
                    ans+=(1ll<<i);
                    nw=nxt[nw].ff;
                }
                else
                {
                    nw= nxt[nw].ss;

                }
            }
        }
        return ans;
    }
};
tk st[4*maxn];
void update(ll id,ll left,ll right,ll x)
{
    if (f[x]>right||f[x]<left) return ;
   st[id].add(val[x]);
   //cout <<id<<" "<<val[x]<<endl;
   if (left==right) return ;
   ll mid=(left+right)/2;
   if (f[x]<=mid) update(id*2,left, mid, x);
   else update(id*2+1, mid+1, right, x);
}
ll get(ll id,ll left,ll right,ll x,ll y,ll p)
{
    if (x>right||y<left) return 0;
  //  cout <<x<<" "<<y<<" "<<left<<" "<<right<<" "<<id<<endl;
    if (x<=left&&y>=right)
    {
       // cout <<"WTF"<<" "<<id<<" "<<p<<endl;
        return st[id].que(p);
    }
    ll mid=(left+right)/2;
    return max(get(id*2, left, mid, x, y, p),get(id*2+1, mid+1, right, x, y, p ));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.ans", "w", stdout);
    }
    ll q;
     cin>> q;
     ll cntnw=1;
     for (int i=1;i<=q;i++)
     {
         string s;
         cin>> s;
         if (s=="Add")
         {
            t[i]=1;
            cin>>a[i].ff>>a[i].ss;
            cntnw++;
            adj[a[i].ff].pb(make_pair(cntnw,a[i].ss));
            a[i].ff=cntnw;
         }
         else
         {
             t[i]=0;
             cin>>a[i].ff>>a[i].ss;
         }
     }
     dfs(1);
     for (int i=1;i<=cntnw;i++)
     {
         adj[i].clear();
         adj[i].shrink_to_fit();
     }
  // cout <<cntnw<<endl;
   // st[1].add(5);
   // cout <<st[1].que(6)<<endl;
     update(1,1,cntnw,1);

     for (int i=1;i<=q;i++)
     {
         if (t[i])
         {
             ll x=a[i].ff;
           //  cout <<a[i].ff<<endl;
             update(1,1,cntnw,x);
         }
         else
         {
             ll nw=val[a[i].ff];
           //  cout <<nw<<" "<<f[a[i].ss]<<" "<<l[a[i].ss]<<endl;
             cout <<get(1,1,cntnw,f[a[i].ss],l[a[i].ss],nw)<<endl;
         }
     }


}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  144 |         freopen("test.ans", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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