Submission #86962

#	Time	Username	Problem	Language	Result	Execution time	Memory
86962		zoooma13	Pictionary (COCI18_pictionary)	C++14	56 / 140	1568 ms	6684 KiB

pictionary

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

#define MAX_N 100005

int N ,M ,Q;
int A[MAX_N] ,B[MAX_N];
int ans[MAX_N];

int Parent[MAX_N];
int Find(int U){
    return Parent[U] = (Parent[U] == U ? U : Find(Parent[U]));
}
void Union(int U ,int V){
    U = Find(U) ,V = Find(V);
    Parent[U] = V;
}

int main()
{
    cin >> N >> M >> Q;
    for(int i=0; i<Q; i++)
        cin >> A[i] >> B[i];

    iota(Parent ,Parent+N+1 ,0);
    for(int i=M; i; i--)
    {
        for(int j=i+i; j<=N; j+=i)
            Union(i ,j);

        for(int j=0; j<Q; j++)
            if(!ans[j] && Find(A[j]) == Find(B[j]))
                ans[j] = M-i+1;
    }

    for(int j=0; j<Q; j++)
        cout << ans[j] << endl;
}

• 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