Submission #1076430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076430		clementine	Pictionary (COCI18_pictionary)	C++17	0 / 140	90 ms	26308 KiB

pictionary

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

int par[100005];
int sz[100005];
// tree after dsu first int is edge, second is weight
vector<pair<int ,int>> graph[100005];
int maxs[100005][20];
int parent[100005][20];
bool visited[100005];
int h[100005];

void construct(int n)
{
    for(int i = 0; i <=n; i ++)
    {
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int a)
{
    if(par[a] !=a)
    {
        par[a] = find(par[a]);
        return par[a];
    }
    return a;
}
void unite(int x, int y, int w)
{
    int a = find(x);
    int b = find(y);
    if(a!=b)
    {
        if(sz[a] > sz[b])
        {
            swap(a, b);
        }
        par[a] = b;
        sz[b] +=sz[a];
        graph[b].push_back({a, w});
        graph[a].push_back({b, w});
    }
}

void dfs(int u )
{
    visited[u] = true;
    for(auto v:graph[u])
    {
        if(!visited[v.first])
        {
            parent[v.first][0] = u;
            maxs[v.first][0] = v.second;
            h[v.first] = h[u] - 1;
            dfs(v.first);
        }
    }
}
int findmin(int x, int y)
{
    int ans = 0;
    if(h[x] < h[y])
    {
        swap(x, y);
    }
    int d = h[x] - h[y];
    for(int i = 0; i <20; i ++)
    {
        if((1<<i) && d)
        {
            ans = max(ans, maxs[x][i]);
            x = parent[x][i];
        }
    }
    for(int i = 19; i >=1; i --)
    {
        if(parent[x][i] != parent[y][i])
        {
            ans = max(ans, maxs[x][i]);
            ans = max(ans, maxs[y][i]);
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    ans = max(ans, maxs[x][0]);
    ans= max(ans, maxs[y][0]);
    return ans;
}





int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> queries;
    for(int i = 0, a, b; i <q; i ++)
    {
        cin >> a >> b;
        queries.push_back({a, b});
    }
    construct(n);
    for(int i = m; i >=1; i --)
    {
        for(int f = 2; f* i <=n; f ++)
        {
            int a =find(i);
            int b = find(f * i);
            if (a!= b)
            {
                unite(a, b,  m - i + 1);
            }
        }
    }
    /*
    for(int i = 1; i <=n; i ++)
    {
        for(auto v: graph[i])
        {
            cout<< i << " " << v.first << " " << v.second << '\n';
        }
    }*/
    int root = find(1);
    maxs[root][0] = 0;
    dfs(root);
    for(int k = 1; (1 << k) <=n; k ++)
    {   
        for(int i = 1; i <=n; i ++)
        {
            maxs[i][k] = max(maxs[i][k-1], maxs[parent[i][k-1]][k-1]);
            parent[i][k] = parent[parent[i][k-1]][k-1];
        }

    }
    for(auto q:queries)
    {
        cout << findmin(q.first, q.second) << '\n';
    }

}

Compilation message (stderr)

pictionary.cpp: In function 'int findmin(int, int)':
pictionary.cpp:71:14: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   71 |         if((1<<i) && d)
      |            ~~^~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 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