oj.uz

Submission #981475

# Submission time Handle Problem Language Result Execution time Memory
981475 2024-05-13T09:05:45 Z vjudge1 Pictionary (COCI18_pictionary) C++17
140 / 140
 125 ms 49680 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 1e6+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,m,q;

struct DSU
{
    int s[SZ], par[SZ];

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            s[i] = 1;
            par[i] = i;
        }
    }

    int get(int u)
    {
        return par[u] == u ? u : par[u] = get(par[u]);
    }

    bool join(int u, int v)
    {
        u = get(u);
        v = get(v);
        if(u == v) return false;
        if(s[u] < s[v]) swap(u, v);
        s[u] += s[v];
        par[v] = u;
        return true;
    }
} dsu;

vector<pii> mst[SZ];

int h[SZ], up[SZ][20], val[SZ][20];

void dfs(int u, int pre)
{
    for(pii e : mst[u])
    {
        int v = e.fi, w = e.se;
        if(v == pre) continue;
        h[v] = h[u] + 1;
        val[v][0] = w;
        up[v][0] = u;
        for(int i = 1; i < 20; i++)
        {
            up[v][i] = up[up[v][i-1]][i-1];
            val[v][i] = max(val[v][i-1], val[up[v][i-1]][i-1]);
        }
        dfs(v, u);
    }
}

int res(int u, int v)
{
    int mx = 0;
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        for(int i = 0; i < 20; i++)
        {
            if(diff >> i & 1)
            {
                mx = max(mx, val[u][i]);
                u = up[u][i];
            }
        }
    }
    if(u == v) return mx;
    for(int i = 19; i >= 0; i--)
    {
        if(up[u][i] != up[v][i])
        {
            mx = max({mx, val[u][i], val[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    return max({mx, val[u][0], val[v][0]});
}

int main()
{
    init();
    cin >> n >> m >> q;
    dsu.init(n);
    for(int i = m; i >= 1; i--)
    {
        for(int j = 2*i; j <= n; j += i)
        {
            int u = j-i, v = j;
            if(dsu.join(u, v))
            {
                mst[u].pb({v, m - i + 1});
                mst[v].pb({u, m - i + 1});
            }
        }
    }
    dfs(1, 0);
    while(q--)
    {
        int u,v;
        cin >> u >> v;
        cout << res(u, v) << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30008 KB Output is correct
2 Correct 25 ms 30044 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30476 KB Output is correct
2 Correct 32 ms 30544 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32868 KB Output is correct
2 Correct 27 ms 32860 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 37544 KB Output is correct
2 Correct 34 ms 37724 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 38684 KB Output is correct
2 Correct 35 ms 38236 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 43348 KB Output is correct
2 Correct 61 ms 43868 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 46524 KB Output is correct
2 Correct 85 ms 49176 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 49492 KB Output is correct
2 Correct 91 ms 49680 KB Output is correct