Submission #632112

#	Time	Username	Problem	Language	Result	Execution time	Memory
632112		arayi	Prize (CEOI22_prize)	C++17	0 / 100	2528 ms	1048576 KiB

Main

// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};

const int N = 2e6 + 20;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 200;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1)
            ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream &operator<<(ostream &c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template <class T>
void maxi(T &a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
    a = min(a, b);
}

int n, k, q, t;
vii g[2][N], g1[2][N];
int l[2], l1[2], pr[2][N][20], xr[2][N];
int s[2][N];
bool cl[N];
void dfs0(int i1, int v, int par, int nx)
{
    if (!cl[v])
    {
        if (nx == -1)
            l1[i1] = v;
        else
            g1[i1][v].ad(nx), g1[i1][nx].ad(v);
        nx = v;
    }
    for (auto p : g[i1][v])
    {
        if (p == par)
            continue;
        dfs0(i1, p, v, nx);
    }
}
void dfs(int i1, int v, int par)
{
    pr[i1][v][0] = par;
    for (auto p : g[i1][v])
    {
        if (p == par)
            continue;
        xr[i1][p] = xr[i1][v] + 1;
        dfs(i1, p, v);
    }
}
int wk(int i1, int u, int d)
{
    for (int i = 0; i < 20; i++)
    {
        if ((1 << i) & d)
            u = pr[i1][u][i];
    }
    return u;
}
int lca(int i1, int u, int v)
{
    if (xr[i1][u] > xr[i1][v])
        swap(u, v);
    v = wk(i1, v, xr[i1][v] - xr[i1][u]);
    if (u == v)
        return u;
    for (int i = 19; i >= 0; i--)
    {
        if (pr[i1][u][i] != pr[i1][v][i])
        {
            u = pr[i1][u][i];
            v = pr[i1][v][i];
        }
    }
    return pr[i1][u][0];
}
int a[N][4], sm[N];
int main()
{
    fastio;
    cin >> n >> k >> q >> t;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == -1)
        {
            l[0] = i;
            continue;
        }
        s[0][x]++;
        pr[0][i][0] = x;
        g[0][x].ad(i);
        g[0][i].ad(x);
    }
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == -1)
        {
            l[1] = i;
            continue;
        }
        s[1][x]++;
        pr[1][i][0] = x;
        g[1][x].ad(i);
        g[1][i].ad(x);
    }
    priority_queue<pir> qq;
    for (int i = 1; i <= n; i++)
        qq.push(MP(-max(s[0][i], s[1][i]), i));
    for (int i = 0; i < n - k; i++)
    {
        auto p = qq.top();
        qq.pop();
        if (cl[p.sc])
            continue;
        if (p.fr < -1)
            assert(0);
        cl[p.sc] = 1;
        if (p.fr == 0)
        {
            s[0][pr[0][p.sc][0]]--;
            s[1][pr[1][p.sc][0]]--;
            qq.push(MP(-max(s[0][pr[0][p.sc][0]], s[1][pr[0][p.sc][0]]), pr[0][p.sc][0]));
            qq.push(MP(-max(s[1][pr[1][p.sc][0]], s[1][pr[1][p.sc][0]]), pr[1][p.sc][0]));
        }
        else if(p.fr == -1)
        {
            g[0][pr[0][p.sc][0]].clear();
            g[0][pr[0][p.sc][0]].ad(g[0][p.sc][0]);
            pr[0][g[0][p.sc][0]][0] = pr[0][p.sc][0];
            g[1][pr[1][p.sc][0]].clear();
            g[1][pr[1][p.sc][0]].ad(g[1][p.sc][0]);
            pr[1][g[1][p.sc][0]][0] = pr[1][p.sc][0];
        }
    }
    dfs0(0, l[0], 0, -1);
    dfs0(1, l[1], 0, -1);
    swap(g, g1), swap(l, l1);
    for (int i = 1; i <= n; i++)
        if (!cl[i])
            cout << i << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        if (i == l[0] || cl[i])
            continue;
        cout << "? " << l[0] << " " << i << endl;
    }
    cout << "!" << endl;
    dfs(0, l[0], l[0]);
    dfs(1, l[1], l[1]);
    for (int i1 : {0, 1})
    {
        for (int i = 1; i < 20; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (cl[j])
                    continue;
                pr[i1][j][i] = pr[i1][pr[i1][j][i - 1]][i - 1];
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (i == l[0] || cl[i])
            continue;
        for (int j = 0; j < 4; j++)
            cin >> a[i][j];
    }
    for (int i = 1; i <= n; i++)
    {
        if (cl[i])
            continue;
        int s = lca(1, i, l[0]);
        sm[i] = a[i][3] - a[s][2] + a[l[1]][2];
        //cout << i << " " << sm[i] << endl;
    }

    for (int i = 0; i < t; i++)
    {
        int u, v;
        cin >> u >> v;
        //cout << lca(0, u, v) << endl;
        cout << a[u][1] + a[v][1] - 2 * a[lca(0, u, v)][1] << " ";
        cout << sm[u] + sm[v] - 2 * sm[lca(1, u, v)] << "\n";
    }

    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

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