oj.uz

Submission #1073429

# Submission time Handle Problem Language Result Execution time Memory
1073429 2024-08-24T14:37:04 Z clementine Pictionary (COCI18_pictionary) C++17
56 / 140
 39 ms 16208 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7604 KB Output is correct
2 Correct 23 ms 7528 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7940 KB Output is correct
2 Correct 29 ms 7644 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 14244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 14428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 14932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 15448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 15700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 16208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -