Submission #1047060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047060		12345678	Pictionary (COCI18_pictionary)	C++17	140 / 140	165 ms	16044 KiB

pictionary

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, m, q, dsu[nx], l[nx], r[nx], res[nx], a[nx], b[nx];
vector<int> qrs[nx];

int find(int x)
{
    if (x==dsu[x]) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    //cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=q; i++) l[i]=1, r[i]=m, cin>>a[i]>>b[i];
    while (1)
    {
        bool f=1;
        for (int i=1; i<=m; i++) qrs[i].clear();
        for (int i=1; i<=n; i++) dsu[i]=i;
        for (int i=1; i<=q; i++) if (l[i]!=r[i]) f=0, qrs[(l[i]+r[i])/2].push_back(i);
        //for (int i=1; i<=q; i++) cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
        if (f) break;
        for (int i=1; i<=m; i++)
        {
            int g=m-i+1;
            for (int j=2*g; j<=n; j+=g) dsu[find(j)]=find(g);
            for (auto x:qrs[i]) 
            {
                if (find(a[x])==find(b[x])) r[x]=i;
                else l[x]=i+1;
            }
        }
    }
    for (int i=1; i<=q; i++) cout<<l[i]<<'\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