oj.uz

Submission #251983

# Submission time Handle Problem Language Result Execution time Memory
251983 2020-07-23T12:11:16 Z Vladikus004 Pictionary (COCI18_pictionary) C++14
140 / 140
 265 ms 29944 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 100000 + 3;
int n, m, q, x[N], y[N], p[N], ans[N];
set <int> ms[N];
vector <int> qs[N];

void init(){
    for (int i = 1; i <= n; i++)
        p[i] = i;
}

int get_anc(int x){
    if (p[x] == x) return x;
    return p[x] = get_anc(p[x]);
}

void unite(int X, int Y, int now){
    X = get_anc(X);
    Y = get_anc(Y);
    if (X == Y) return;
    if (ms[X].size() > ms[Y].size()) swap(X, Y);
    for (auto u: ms[X]){
        for (auto it: qs[u]){
            int e = x[it] + y[it] - u;
            if (ms[Y].count(e))
                ans[it] = now;
        }
    }
    p[X] = Y;
    ms[Y].insert(all(ms[X]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m >> q;
    init();
    for (int i = 0; i < q; i++){
        cin >> x[i] >> y[i];
        qs[x[i]].push_back(i);
        qs[y[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        ms[i].insert(i);
    int cnt = 1;
    for (int i = m; i > 0; i--){
        for (int j = i * 2; j <= n; j += i){
            unite(j, j - i, cnt);
        }
        cnt++;
    }
//    for (auto u: ms[6]) cout << u << " "; cout << "\n";
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9856 KB Output is correct
2 Correct 37 ms 9996 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11000 KB Output is correct
2 Correct 49 ms 10620 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13284 KB Output is correct
2 Correct 61 ms 13236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15096 KB Output is correct
2 Correct 84 ms 14328 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 18476 KB Output is correct
2 Correct 104 ms 18112 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 17656 KB Output is correct
2 Correct 198 ms 23544 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 25336 KB Output is correct
2 Correct 224 ms 26872 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 29944 KB Output is correct
2 Correct 259 ms 29304 KB Output is correct