oj.uz

Submission #858393

# Submission time Handle Problem Language Result Execution time Memory
858393 2023-10-08T10:48:13 Z Hanksburger Pictionary (COCI18_pictionary) C++17
140 / 140
 88 ms 27372 KB 
#include <bits/stdc++.h>
using namespace std;
int p[200005][20], depth[200005], par[200005];
vector<int> child[200005];
int findPar(int u)
{
    return (par[u]==u)?u:(par[u]=findPar(par[u]));
}
void dfs(int u)
{
    for (int v:child[u])
    {
        depth[v]=depth[u]+1;
        dfs(v);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<=n+m; i++)
        par[i]=i;
    for (int i=1; i<=m; i++)
    {
        for (int u=m-i+1; u<=n; u+=m-i+1)
        {
            int v=findPar(u);
            if (v<n+i)
            {
                p[v][0]=par[v]=n+i;
                child[n+i].push_back(v);
            }
        }
    }
    for (int i=1; i<20; i++)
        for (int j=1; j<=n+m; j++)
            p[j][i]=p[p[j][i-1]][i-1];
    dfs(n+m);
    for (int i=1; i<=q; i++)
    {
        int u, v;
        cin >> u >> v;
        if (depth[u]<depth[v])
            swap(u, v);
        int x=depth[u]-depth[v];
        for (int j=0; j<20; j++)
            if (x&(1<<j))
                u=p[u][j];
        if (u==v)
        {
            cout << u-n << '\n';
            continue;
        }
        for (int j=19; j>=0; j--)
        {
            if (p[u][j]!=p[v][j])
            {
                u=p[u][j];
                v=p[v][j];
            }
        }
        cout << p[u][0]-n << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7000 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9564 KB Output is correct
2 Correct 21 ms 7516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10068 KB Output is correct
2 Correct 27 ms 9808 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12368 KB Output is correct
2 Correct 20 ms 11868 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12380 KB Output is correct
2 Correct 21 ms 11864 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17500 KB Output is correct
2 Correct 27 ms 14396 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14416 KB Output is correct
2 Correct 50 ms 17364 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 22356 KB Output is correct
2 Correct 58 ms 19592 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 27372 KB Output is correct
2 Correct 51 ms 20024 KB Output is correct