oj.uz

Submission #1073431

# Submission time Handle Problem Language Result Execution time Memory
1073431 2024-08-24T14:39:52 Z DeathIsAwe Pictionary (COCI18_pictionary) C++17
140 / 140
 96 ms 24276 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17244 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17552 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17876 KB Output is correct
2 Correct 29 ms 17880 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18164 KB Output is correct
2 Correct 34 ms 17924 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 19116 KB Output is correct
2 Correct 27 ms 19048 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 19712 KB Output is correct
2 Correct 34 ms 19928 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20692 KB Output is correct
2 Correct 35 ms 20696 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 21676 KB Output is correct
2 Correct 59 ms 22220 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22740 KB Output is correct
2 Correct 67 ms 23520 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 24192 KB Output is correct
2 Correct 74 ms 24276 KB Output is correct