oj.uz

Submission #466142

# Submission time Handle Problem Language Result Execution time Memory
466142 2021-08-18T06:24:01 Z Radman_ Klasika (COCI20_klasika) C++14
110 / 110
 3063 ms 473840 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++;
	return;
}

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])
		{
			if(cur->child[y]->s.size())
			{
				auto it=cur->child[y]->s.lower_bound(st[b]);
				if(it!=cur->child[y]->s.end())
				{
					if(*it<=et[b])
					{
						cur=cur->child[y];
						ans+='1';
						continue;
					}
				}
			}
		}
		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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5580 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 6 ms 5452 KB Output is correct
12 Correct 5 ms 5580 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5580 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 6 ms 5452 KB Output is correct
12 Correct 5 ms 5580 KB Output is correct
13 Correct 12 ms 6568 KB Output is correct
14 Correct 12 ms 8012 KB Output is correct
15 Correct 13 ms 9380 KB Output is correct
16 Correct 15 ms 10664 KB Output is correct
17 Correct 12 ms 6460 KB Output is correct
18 Correct 14 ms 7864 KB Output is correct
19 Correct 14 ms 9292 KB Output is correct
20 Correct 15 ms 10572 KB Output is correct
21 Correct 12 ms 6464 KB Output is correct
22 Correct 13 ms 7884 KB Output is correct
23 Correct 14 ms 9292 KB Output is correct
24 Correct 14 ms 10532 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 131720 KB Output is correct
2 Correct 1662 ms 250596 KB Output is correct
3 Correct 2260 ms 361652 KB Output is correct
4 Correct 2605 ms 473456 KB Output is correct
5 Correct 1297 ms 132424 KB Output is correct
6 Correct 1815 ms 246440 KB Output is correct
7 Correct 2247 ms 355612 KB Output is correct
8 Correct 2856 ms 464620 KB Output is correct
9 Correct 1346 ms 131904 KB Output is correct
10 Correct 1873 ms 247368 KB Output is correct
11 Correct 2379 ms 358152 KB Output is correct
12 Correct 2733 ms 466768 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5580 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 6 ms 5452 KB Output is correct
12 Correct 5 ms 5580 KB Output is correct
13 Correct 12 ms 6568 KB Output is correct
14 Correct 12 ms 8012 KB Output is correct
15 Correct 13 ms 9380 KB Output is correct
16 Correct 15 ms 10664 KB Output is correct
17 Correct 12 ms 6460 KB Output is correct
18 Correct 14 ms 7864 KB Output is correct
19 Correct 14 ms 9292 KB Output is correct
20 Correct 15 ms 10572 KB Output is correct
21 Correct 12 ms 6464 KB Output is correct
22 Correct 13 ms 7884 KB Output is correct
23 Correct 14 ms 9292 KB Output is correct
24 Correct 14 ms 10532 KB Output is correct
25 Correct 1227 ms 131720 KB Output is correct
26 Correct 1662 ms 250596 KB Output is correct
27 Correct 2260 ms 361652 KB Output is correct
28 Correct 2605 ms 473456 KB Output is correct
29 Correct 1297 ms 132424 KB Output is correct
30 Correct 1815 ms 246440 KB Output is correct
31 Correct 2247 ms 355612 KB Output is correct
32 Correct 2856 ms 464620 KB Output is correct
33 Correct 1346 ms 131904 KB Output is correct
34 Correct 1873 ms 247368 KB Output is correct
35 Correct 2379 ms 358152 KB Output is correct
36 Correct 2733 ms 466768 KB Output is correct
37 Correct 1727 ms 135648 KB Output is correct
38 Correct 2270 ms 250620 KB Output is correct
39 Correct 2526 ms 364668 KB Output is correct
40 Correct 2800 ms 473840 KB Output is correct
41 Correct 1971 ms 133096 KB Output is correct
42 Correct 2421 ms 246552 KB Output is correct
43 Correct 2878 ms 355836 KB Output is correct
44 Correct 3063 ms 463760 KB Output is correct
45 Correct 2041 ms 132376 KB Output is correct
46 Correct 2563 ms 247676 KB Output is correct
47 Correct 2771 ms 356820 KB Output is correct
48 Correct 3005 ms 466860 KB Output is correct