oj.uz

답안 #237530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237530 2020-06-07T07:43:31 Z kartel Pictionary (COCI18_pictionary) C++14
0 / 140
 228 ms 25828 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;

    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;

    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 + i; 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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 2816 KB Output isn't correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2944 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 3200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 3324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 7936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 10072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 13432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 17272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 20728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 228 ms 25828 KB Output isn't correct
2 Halted 0 ms 0 KB -