oj.uz

Submission #466131

# Submission time Handle Problem Language Result Execution time Memory
466131 2021-08-18T04:24:21 Z Radman_ Klasika (COCI20_klasika) C++14
0 / 110
 1275 ms 133144 KB 
//                  //
//     Radmanシ     //
//                 //
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<math.h>

using namespace std;

/*#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")*/

//#define int long long

typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
#define F first
#define S second

struct Node
{
    Node *child[2];
    Node *par=nullptr;
    int height,id,cnt;
    set<int> s;
    Node()
    {
        height=-1;
        id=-1;
        cnt=0;
        for(int i=0;i<2;i++)
            child[i]=nullptr;
    }
};

struct Trie
{
    Node *root;
    int strType,cnt;
    Trie()
    {
        strType='0';
        cnt=1;
        root=new Node();
        root->height=0;
        root->id=1;
    }
    void add(string st,int num)
    {
        Node *cur=root;
        cur->cnt++;
        cur->s.insert(num);
        for(char c:st)
        {
            int x=int(c)-strType;
            if(cur->child[x]==nullptr)
            {
                cur->child[x]=new Node();
                Node *next=cur->child[x];
                next->par=cur;
                next->height=cur->height+1;
                next->id=++cnt;
            }
            cur=cur->child[x];
            cur->cnt++;
            cur->s.insert(num);
        }
        return;
    }
};

string mabnaye2(int n)
{
    string ans;
    while(n>0)
    {
        ans+=to_string(n%2);
        n/=2;
    }
    reverse(ans.begin(),ans.end());
    while(ans.size()<31)
    	ans='0'+ans;
    return ans;
}

int decimal(string s)
{
	int ans=0,po=1;
	for(int i=s.size()-1;i>=0;i--)
	{
		ans+=(s[i]=='1')*po;
		po*=2;
	}
	return ans;
}

const int maxn=2e5+5;
int st[maxn],et[maxn],Xor[maxn];
vector<pii> yal[maxn];
vector<pip> query;
int tim=0;

void dfs(int now)
{
	st[now]=tim++;
	for(int i=0;i<(int)yal[now].size();i++)
	{
		Xor[yal[now][i].F]=(Xor[now]^yal[now][i].S);
		dfs(yal[now][i].F);
	}
	et[now]=tim++;
}

string find(int a,int b,Node *root)
{

	string mab=mabnaye2(Xor[a]),ans="";
	Node *cur=root;
	for(char c:mab)
	{
		int x=c-'0';
		int y=(x^1);
		if(cur->child[y])
		{
			int s=*cur->child[y]->s.lower_bound(st[b]);
			if(s<=et[b])
			{
				cur=cur->child[y];
				ans+='1';
				continue;
			}
		}
		if(cur->child[x])
		{
			cur=cur->child[x];
			ans+='0';
		}
	}
	return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int Q;
    cin>>Q;
    int id=1;
    for(int i=0;i<Q;i++)
    {
        string s;
        int a,b;
        cin>>s>>a>>b;
        if(s=="Add")
        {
        	yal[a].push_back(pii(++id,b));
        	query.push_back(pip(1,pii(id,0)));
        }
        else
        {
        	yal[a].push_back(pii(++id,b));
        	query.push_back(pip(2,pii(a,b)));
        }
    }
    dfs(1);
    Trie *T=new Trie();
    T->add(mabnaye2(Xor[1]),st[1]);
    for(int q=0;q<Q;q++)
    {
        int qt=query[q].F;
        if(qt==1)
        {
            int x=query[q].S.F;
            T->add(mabnaye2(Xor[x]),st[x]);
        }
        else
        {
            int a=query[q].S.F,b=query[q].S.S;
            string ret=find(a,b,T->root);
            cout<<decimal(ret)<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1275 ms 133144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5188 KB Output isn't correct
2 Halted 0 ms 0 KB -