Submission #858393

#	Time	Username	Problem	Language	Result	Execution time	Memory
858393		Hanksburger	Pictionary (COCI18_pictionary)	C++17	140 / 140	88 ms	27372 KiB

pictionary

#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 / 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