Submission #1073429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073429		clementine	Pictionary (COCI18_pictionary)	C++17	56 / 140	39 ms	16208 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

pair<int, int> qs[100005];
int par[100005];
int sz[100005];
int ans[1003][1003];
vector<int> graph[100005];

void construct(int n)
{
    for(int i = 1; i <=n; i ++)
    {
        sz[i] = 0;
        par[i] = i;
    }
}
int find(int a)
{
    if(par[a] !=a)
    {
        par[a] = find(par[a]);
        return par[a];
    }
    return a;
}
void unite(int a, int b)
{
    int x= find(a);
    int y = find(b);
    if(x!=y)
    {
        if(sz[y] > sz[x])
        {
            swap(x, y);
        }
        par[y] = x;
        graph[x].push_back(y);
        sz[x] += sz[y];
    }
}
vector<int> groupx, groupy;
void dfs(int u)
{
    groupx.push_back(u);
    for(auto v:graph[u])
    {
        dfs(v);
    }
}

void dfs2(int u)
{
    groupy.push_back(u);
    for(auto v:graph[u])
    {
        dfs2(v);
    }
}

int main()
{
    int n ,m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <=q; i ++)
    {
        cin >> qs[i].first >> qs[i].second;
    }
    construct(n);
    for(int i = m; i >=1; i --)
    {
        int x = find(i);
        for(int f = 2; f * i <=n; f ++)
        {
            int y = find(f*i);
            
            if(x!= y)
            {
                 groupx.clear();
                dfs(x);
                /*
                for(auto g:groupx)
                {
                    cout << g << " " << i << " ";
                }
                cout << "g\n";  */
                groupy.clear();
                dfs2(y);
                /*
                for(auto g:groupy)
                {
                    cout << g << " " << f << " ";
                }
                cout << "h\n";  */
                for(auto g: groupx)
                {
                    for(auto h: groupy)
                    {
                        ans[g][h] = ans[h][g] = m - i + 1;
                    }
                }
                unite(x, y);
                x = find(x);
            }
        }
    }

    for(int i = 1; i <=q; i ++)
    {
        cout << ans[qs[i].first][qs[i].second] << '\n';
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14