oj.uz

Submission #334968

# Submission time Handle Problem Language Result Execution time Memory
334968 2020-12-10T13:49:26 Z Dymo Klasika (COCI20_klasika) C++14
33 / 110
 1420 ms 524292 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30188 KB Output is correct
2 Correct 21 ms 30316 KB Output is correct
3 Correct 22 ms 30444 KB Output is correct
4 Correct 22 ms 30572 KB Output is correct
5 Correct 21 ms 30188 KB Output is correct
6 Correct 21 ms 30316 KB Output is correct
7 Correct 21 ms 30444 KB Output is correct
8 Correct 22 ms 30572 KB Output is correct
9 Correct 21 ms 30188 KB Output is correct
10 Correct 21 ms 30336 KB Output is correct
11 Correct 22 ms 30444 KB Output is correct
12 Correct 22 ms 30572 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30188 KB Output is correct
2 Correct 21 ms 30316 KB Output is correct
3 Correct 22 ms 30444 KB Output is correct
4 Correct 22 ms 30572 KB Output is correct
5 Correct 21 ms 30188 KB Output is correct
6 Correct 21 ms 30316 KB Output is correct
7 Correct 21 ms 30444 KB Output is correct
8 Correct 22 ms 30572 KB Output is correct
9 Correct 21 ms 30188 KB Output is correct
10 Correct 21 ms 30336 KB Output is correct
11 Correct 22 ms 30444 KB Output is correct
12 Correct 22 ms 30572 KB Output is correct
13 Correct 27 ms 31468 KB Output is correct
14 Correct 30 ms 33000 KB Output is correct
15 Correct 32 ms 34208 KB Output is correct
16 Correct 35 ms 36088 KB Output is correct
17 Correct 25 ms 31468 KB Output is correct
18 Correct 29 ms 33132 KB Output is correct
19 Correct 31 ms 34028 KB Output is correct
20 Correct 34 ms 35684 KB Output is correct
21 Correct 26 ms 31468 KB Output is correct
22 Correct 29 ms 32748 KB Output is correct
23 Correct 32 ms 34024 KB Output is correct
24 Correct 34 ms 35684 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 196416 KB Output is correct
2 Correct 1042 ms 369656 KB Output is correct
3 Runtime error 1420 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30188 KB Output is correct
2 Correct 21 ms 30316 KB Output is correct
3 Correct 22 ms 30444 KB Output is correct
4 Correct 22 ms 30572 KB Output is correct
5 Correct 21 ms 30188 KB Output is correct
6 Correct 21 ms 30316 KB Output is correct
7 Correct 21 ms 30444 KB Output is correct
8 Correct 22 ms 30572 KB Output is correct
9 Correct 21 ms 30188 KB Output is correct
10 Correct 21 ms 30336 KB Output is correct
11 Correct 22 ms 30444 KB Output is correct
12 Correct 22 ms 30572 KB Output is correct
13 Correct 27 ms 31468 KB Output is correct
14 Correct 30 ms 33000 KB Output is correct
15 Correct 32 ms 34208 KB Output is correct
16 Correct 35 ms 36088 KB Output is correct
17 Correct 25 ms 31468 KB Output is correct
18 Correct 29 ms 33132 KB Output is correct
19 Correct 31 ms 34028 KB Output is correct
20 Correct 34 ms 35684 KB Output is correct
21 Correct 26 ms 31468 KB Output is correct
22 Correct 29 ms 32748 KB Output is correct
23 Correct 32 ms 34024 KB Output is correct
24 Correct 34 ms 35684 KB Output is correct
25 Correct 579 ms 196416 KB Output is correct
26 Correct 1042 ms 369656 KB Output is correct
27 Runtime error 1420 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -