oj.uz

Submission #1047060

# Submission time Handle Problem Language Result Execution time Memory
1047060 2024-08-07T08:22:40 Z 12345678 Pictionary (COCI18_pictionary) C++17
140 / 140
 165 ms 16044 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8292 KB Output is correct
2 Correct 24 ms 7372 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9628 KB Output is correct
2 Correct 32 ms 8660 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8720 KB Output is correct
2 Correct 41 ms 8400 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9304 KB Output is correct
2 Correct 38 ms 8140 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11344 KB Output is correct
2 Correct 67 ms 9080 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9416 KB Output is correct
2 Correct 106 ms 12488 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14216 KB Output is correct
2 Correct 126 ms 12996 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 16044 KB Output is correct
2 Correct 144 ms 14448 KB Output is correct