oj.uz

Submission #237557

# Submission time Handle Problem Language Result Execution time Memory
237557 2020-06-07T10:15:12 Z kartel Pictionary (COCI18_pictionary) C++14
140 / 140
 175 ms 25976 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2944 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3320 KB Output is correct
2 Correct 48 ms 3328 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3320 KB Output is correct
2 Correct 60 ms 3512 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7928 KB Output is correct
2 Correct 46 ms 8184 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10108 KB Output is correct
2 Correct 78 ms 11360 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13408 KB Output is correct
2 Correct 72 ms 14200 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17216 KB Output is correct
2 Correct 135 ms 19064 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 20828 KB Output is correct
2 Correct 165 ms 23672 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 25848 KB Output is correct
2 Correct 175 ms 25976 KB Output is correct