Submission #1194113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194113		Zbyszek99	Prize (CEOI22_prize)	C++20	0 / 100	3213 ms	369084 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct edge
{
    int d1,d2;
    ll d;
};

bool used[1000'001];
bool used2[1000'001];
vi query_list;
int used_cnt = 0;
int n,k,q,t;

struct tree
{   
    vi T[1000'001];
    ll root_dist[1000'001];
    int P[1000'001];
    int jump[1000'001][20];
    int dist[1000'001];
    int root;
    tree()
    {
        rep2(i,1,1000'000) 
        {
            T[i] = {};
            root_dist[i] = 0;
            P[i] = i;
        }
    }
    void dfs_dist(int v, int d)
    {
        dist[v] = d++;
        forall(it,T[v])
        {
            dfs_dist(it,d);
        }
    }
    void calc_jump(bool is_d = 1)
    {
        if(is_d) dfs_dist(root,0);
        rep2(i,1,n) jump[i][0] = P[i];
        rep2(bit,1,19)
        {
            rep2(i,1,n)
            {
                jump[i][bit] = jump[jump[i][bit-1]][bit-1];
            }
        }
    }
    int lca(int a, int b)
    {
        if(a == b) return a;
        if(dist[a] < dist[b]) swap(a,b);
        for(int bit = 19; bit >= 0; bit--)
        {
            if(dist[a] - (1 << bit) >= dist[b])
            {
                a = jump[a][bit];
            }
        }
        if(a == b) return a;
        for(int bit = 19; bit >= 0; bit--)
        {
            if(jump[a][bit] != jump[b][bit])
            {
                a = jump[a][bit];
                b = jump[b][bit];
            }
        }
        return jump[a][0];
    }
    void gen_set(int v)
    {
        if(used_cnt == k) return;
        used_cnt++;
        used[v] = 1;
        forall(it,T[v])
        {
            gen_set(it);
        }
    }
    void gen_query(int v)
    {
        if(used[v])
        {
            used2[v] = 1;
            if(siz(query_list) == 0) query_list.pb(v);
            else
            {
                int l = lca(query_list.back(),v);
                used2[l] = 1;
                cout << "? " << query_list.back() << " " << v << "\n";
                query_list.pb(v);
            }
        }
        forall(it,T[v])
        {
            gen_query(it);
        }
    }
    void gen_new_tree(int v, int prev, int prev_ok, int d)
    {
        if(used[v])
        {
            dist[v] = d++;
            if(prev_ok == -1)
            {
                P[v] = v;
            }
            else
            {
                P[v] = prev_ok;
            }
            prev_ok = v;
        }
        forall(it,T[v])
        {
            if(it != prev)
            {
                gen_new_tree(it,v,prev_ok,d);
            }
        }
    }
    void calc_tree(vi u, vector<edge> e)
    {
        int new_root = e[0].d1;
        root = new_root;
        rep2(i,1,n) if(P[i] != i) T[i].pb(P[i]);
        rep2(i,1,n) used[i] = 0;
        forall(it,u) used[it] = 1;
        rep2(i,1,n) P[i] = i;
        gen_new_tree(new_root,new_root,-1,0);
        calc_jump(0);
        rep2(i,1,n) root_dist[i] = 0;
        vi lcas;
        rep(i,siz(e))
        {
            lcas.pb(lca(e[i].d1,e[i].d2));
        }
        rep2(bit,1,30)
        {
            rep(i,siz(e))
            {
                auto it = e[i];
                root_dist[it.d2] = (it.d - root_dist[it.d1] + 2 * root_dist[lcas[i]] + 6*(1LL << (ll)bit)) % (1LL << (ll)bit); 
            }
        }
    }
    ll real_dist(int a, int b)
    {
        return root_dist[a] + root_dist[b] - 2 * root_dist[lca(a,b)];
    }
};

tree T[2];

int main()
{
    cin >> n >> k >> q >> t;
    rep(d,2)
    {
        rep2(i,1,n)
        {
            int x;
            cin >> x;
            T[d].P[i] = x;
            if(x != -1) T[d].T[x].pb(i);
            else 
            {
                T[d].root = i;
                T[d].P[i] = i;
            }
        }
    }
    T[0].gen_set(T[0].root);
    rep2(i,1,n)
    {
        if(used[i]) 
        {
            cout << i << " ";
        }
    }
    cout << "\n";
    T[0].calc_jump();
    T[1].calc_jump();
    T[1].gen_query(T[1].root);
    cout << "!\n";
    cout.flush();
    vector<edge> e1;
    vector<edge> e2;
    rep(i,k-1)
    {
        ll a,b,c,d;
        cin >> a >> b >> c >> d;
        int l1 = T[0].lca(query_list[i],query_list[i+1]);
        if(l1 != query_list[i] && l1 != query_list[i+1])
        {
            e1.pb({query_list[i],l1,a});
            e1.pb({l1,query_list[i+1],b});
        }
        else
        {
            e1.pb({query_list[i],query_list[i+1],a+b});
        }
        int l2 = T[1].lca(query_list[i],query_list[i+1]);
        if(l2 != query_list[i] && l2 != query_list[i+1])
        {
            e2.pb({query_list[i],l2,c});
            e2.pb({l2,query_list[i+1],d});
        }
        else
        {
            e2.pb({query_list[i],query_list[i+1],c+d});
        }
    }
    vi u1;
    vi u2;
    rep2(i,1,n) if(used[i]) u1.pb(i);
    rep2(i,1,n) if(used2[i]) u2.pb(i);
    T[0].calc_tree(u1,e1);
    T[1].calc_tree(u2,e2);
    rep(qq,t)
    {
        int a,b;
        cin >> a >> b;
        cout << T[0].real_dist(a,b) << " " << T[1].real_dist(a,b) << "\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24