제출 #1360857

#제출 시각아이디문제언어결과실행 시간메모리
1360857po_rag526Selling RNA Strands (JOI16_selling_rna)C++20
0 / 100
1596 ms14260 KiB
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;
#define fori(size) for(int i=0;i<size;i++)
const int MAXN = 1e6 + 5;
const int alpha =26;
const int zero ='0';

struct Trie {
    struct Node
    {
        int p[2];
        int cnt;
        Node()
        {
            memset(p, 0, sizeof p);
            cnt = 0;
        }
    };

    vector<Node> tree;

    Trie()
    {
        tree.push_back(Node());
    }

    void insert(const string &s)
    {
        int cur = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = s[i] - '0';

            tree[cur].cnt++;
            if (!tree[cur].p[c])
            {
                tree[cur].p[c] = tree.size();
                tree.push_back(Node());

            }
            cur = tree[cur].p[c];

        }

        tree[cur].cnt++;

    }

    ll query(const string &s)
    {
        ll cur = 0,sum=0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = s[i] - '0';
            if (tree[cur].p[c])
            {
                cur = tree[cur].p[c];
            }else
                            sum|=1ll<<(31-i),cur = tree[cur].p[!c];
        }
        return sum;
    }

    void del(const string &s)
    {

        int cur = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int c = s[i] - '0';
            int prev = cur;
            cur = tree[cur].p[c];
            if (tree[cur].cnt == 1)
                tree[prev].p[c] = 0;
            tree[cur].cnt--;
        }
    }






};

string tobin(ll d){
    string res;
    fori(32)if((1ll<<i)&d)res='1'+res;else res='0'+res;
    return res;
}
typedef vector<ll> vec;
const ll N=1e5+22;
vec lol(N+1);
vector<vec> adj(N+1);
vector<bool>vis(N+1,0);
vec anss(N);
Trie tr=Trie();
ll mx[N];
ll dfs(ll u=1,ll par=-1) {

    ll ans=tr.query(tobin(lol[u]));
    tr.insert(tobin(lol[u]));
    for (auto v:adj[u]) {
       if (par!=v) {
           dfs(v,u);
           ans=min(ans,anss[v]);
       }
    }
    anss[u]=ans;
    tr.del(tobin(lol[u]));
    return ans;

}
void wowy(){
    ll n;
    ll m;
    cin>>n;
tr.insert(string(32,'1'));
    fori(n-1) {
        ll p;
        cin>>p;
        adj[p].push_back(2+i);
        adj[i+2].push_back(p);


    }
    fori(n)cin>>lol[i+1];
    dfs();
    cin>>m;
    ll c;
    while (m--)cin>>c,cout<<anss[c]<<endl;
}
//OWVX
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
       wowy();
}
//this is O but i have no placce to put in sry xD
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…