Submission #237557

#	Time	Username	Problem	Language	Result	Execution time	Memory
237557		kartel	Pictionary (COCI18_pictionary)	C++14	140 / 140	175 ms	25976 KiB

pictionary

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
//#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

int tin[N], tout[N], up[N][22], sptb[N][22], i, n, m, q, j, v, u, x, y, tim, pr[N], ra[N];
vector <pair <int, int> > g[N];

int ispred(int v, int u) {return (tin[v] <= tin[u] && tout[v] >= tout[u]);}

int lca(int v, int u)
{
    if (ispred(v, u)) return v;
    if (ispred(u, v)) return u;

    for (int st = 20; st >= 0; st--)
        if (!ispred(up[v][st], u))
            v = up[v][st];

    return up[v][0];
}

int get(int v, int u, int lc)
{
    int mx = 0;

    if (v != lc)
    {
        for (int st = 20; st >= 0; st--)
            if (!ispred(up[v][st], lc))
        {
            mx = max(mx, sptb[v][st]);
            v = up[v][st];
        }

        mx = max(mx, sptb[v][0]);
    }

    v = u;

    if (v != lc)
    {
        for (int st = 20; st >= 0; st--)
            if (!ispred(up[v][st], lc))
        {
            mx = max(mx, sptb[v][st]);
            v = up[v][st];
        }

        mx = max(mx, sptb[v][0]);
    }

//    cout << lc << endl;

    return mx;
}

void dfs(int v, int pr, int val)
{
    tin[v] = tim++;
    up[v][0] = pr;
    sptb[v][0] = val;

    for (auto u : g[v])
    {
        if (u.F == pr) continue;
        dfs(u.F, v, u.S);
    }

    tout[v] = tim++;
}

int f(int x)
{
    if (pr[x] != x) pr[x] = f(pr[x]);
    return pr[x];
}

void link(int x, int y)
{
    g[x].pb({y, m - x + 1});
    g[y].pb({x, m - x + 1});

    x = f(x);
    y = f(y);

    if (x < y) swap(x, y);

    if (ra[x] > ra[y]) pr[y] = x;
    else
    {
        pr[x] = y;
        if (ra[x] == ra[y]) ra[y]++;
    }
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n >> m >> q;

    for (i = 1; i <= n; i++) pr[i] = i, ra[i] = 1;

    for (i = m; i >= 1; i--)
       for (j = i * 2; j <= n; j += i)
        if (f(i) != f(j))
            link(i, j);

    tin[0] = -1;
    tout[0] = N * 2;
    tim = 1;

    dfs(1, 0, 0);

    for (int st = 1; st <= 20; st++)
    {
        for (v = 1; v <= n; v++)
        {
            up[v][st] = up[up[v][st - 1]][st - 1];
            sptb[v][st] = max(sptb[v][st - 1], sptb[up[v][st - 1]][st - 1]);
        }
    }

    while (q--)
    {
        cin >> x >> y;

        cout << get(x, y, lca(x, y)) << el;
    }

}

//  x ^ 2 + y ^ 2 = 1
//  x * a_i + y * b_i
//  a_i = -b_i * tan(alpha)
//  a_i / -b_i = tan(alpha)
//  alpha = atan(a_i / (-b_i))

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14