Submission #1073431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073431		DeathIsAwe	Pictionary (COCI18_pictionary)	C++17	140 / 140	96 ms	24276 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
int parent[100001], ranc[100001], height[100001];
pair<int,int> binjump[100001][20];


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


void join(int x, int y) {
    int px = find(x), py = find(y);
    if (ranc[px] > ranc[py]) {
        parent[py] = px;
    } else if (ranc[px] < ranc[py]) {
        parent[px] = py;
    } else {
        parent[py] = px;
        ranc[px]++;
    }
}


int maxpath(int a, int b) {
    if (height[a] < height[b]) {
        swap(a, b);
    }
    int diffh = height[a] - height[b], ans = -1;
    for (int i=0;i<20;i++) {
        if ((diffh>>i) & 1) {
            ans = max(ans, binjump[a][i].second);
            a = binjump[a][i].first;
        }
    }
    if (a == b) {
        return ans;
    }
    for (int i=19;i>-1;i--) {
        //cout << binjump[a][i].first << ' ' << binjump[b][i].first << '\n';
        if (binjump[a][i].first != binjump[b][i].first) {
            ans = max(ans, binjump[a][i].second);
            ans = max(ans, binjump[b][i].second);
            a = binjump[a][i].first;
            b = binjump[b][i].first;
        }
    }
    ans = max(ans, binjump[a][0].second);
    ans = max(ans, binjump[b][0].second);
    return ans;
}


int main() {
    for (int i=0;i<100001;i++) {
        parent[i] = i; 
        ranc[i] = 1;
        height[i] = -1;
        for (int j=0;j<20;j++) {
            binjump[i][j] = make_pair(-1, -1);
        }
    }
    int n, m, q; cin >> n >> m >> q;
    vector<vector<pair<int,int>>> tree(n+1);
    for (int i=m;i>0;i--) {
        for (int j=2*i;j<n+1;j+=i) {
            if (find(j - i) != find(j)) {
                join(j - i, j);
                tree[j - i].push_back(make_pair(j, m - i + 1));
                tree[j].push_back(make_pair(j - i, m - i + 1));
            }
        }
    }
    stack<pair<int,int>> stac; stac.push(make_pair(1, 0));
    pair<int,int> curpair;
    parent[1] = 0;
    binjump[1][0] = make_pair(1, 0);
    while (stac.size() > 0) {
        curpair = stac.top(); stac.pop();
        height[curpair.first] = curpair.second;
        for (pair<int,int> i: tree[curpair.first]) {
            if (height[i.first] == -1) {
                stac.push(make_pair(i.first, curpair.second + 1));
                binjump[i.first][0] = make_pair(curpair.first, i.second);
            }
        }
    }
    int ahead;
    for (int j=1;j<20;j++) {
        for (int i=1;i<n+1;i++) {
            ahead = binjump[i][j - 1].first;
            binjump[i][j] = make_pair(binjump[ahead][j-1].first, max(binjump[i][j-1].second, binjump[ahead][j-1].second));
        }
    }

    /*
    for (int i=1;i<n+1;i++) {
        cout << i << " : ";
        for (pair<int,int> j: tree[i]) {
            cout << '(' << j.first << ' ' << j.second << ") ";
        }
        cout << '\n';
    }
    
    
    for (int i=1;i<n+1;i++) {
        cout << i << " : ";
        for (int j=0;j<6;j++) {
            cout << '(' << binjump[i][j].first << ' ' << binjump[i][j].second << ") ";
        }
        cout << '\n';
    }
    */
    

    vector<int> ansvec;
    int query1, query2;
    for (int i=0;i<q;i++) {
        cin >> query1 >> query2;
        ansvec.push_back(maxpath(query1, query2));
    }
    for (int i: ansvec) {
        cout << 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