Submission #251970

#	Time	Username	Problem	Language	Result	Execution time	Memory
251970		Vladikus004	Pictionary (COCI18_pictionary)	C++14	0 / 140	1592 ms	10372 KiB

pictionary

#include <bits/stdc++.h>
#define int long long
#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, p[N], us[N], code[N], r[N], sz, ans[N];
vector <pii> a;
vector <int> d;
vector <vector <int> > v;

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){
    x = get_anc(x);
    y = get_anc(y);
    if (x == y) return;
    if (rand() & 1) swap(x, y);
    p[x] = y;
}

void fact(int x, int ind){
    for (int i = 2; i * i <= x; i++){
        if (x % i == 0){
            v[code[i]].push_back(ind);
        }
        while (x % i == 0) x /= i;
    }
    if (x != 1) v[code[x]].push_back(ind);
}

void resh(){
    for (int i = 2; i < N; i++){
        if (!r[i]){
            code[i] = sz;
            sz++;
            for (ll j = i * 1LL * i; j < N; j++){
                r[j] = 1;
            }
        }
    }
    v.resize(sz);
}

int lcm(int x, int y){
    return x / __gcd(x, y) * y;
}

void make_d(int x){
    d.clear();
    for (int i = 2; i * i <= x; i++){
        if (x % i == 0) d.push_back(i);
        while (x % i == 0) x/=i;
    }
    if (x != 1) d.push_back(x);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m >> q;
    init();
    resh();
    for (int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        fact(lcm(x, y), i);
        a.push_back({x, y});
        ans[i] = inf;
    }
    int cnt = 1;
    for (int i = m; i > 1; i--){
        for (int j = 2 * i; j <= n; j += i){
            unite(j, j - i);
        }
        make_d(i);
        for (auto u: d)
        for (int j = 0; j < v[code[u]].size(); j++){
            if (us[v[code[u]][j]]){
                swap(v[code[u]][j], v[code[u]][v[code[u]].size() - 1]);
                v[code[u]].pop_back();
                --j;
                continue;
            }
            if (get_anc(a[v[code[u]][j]].first)==get_anc(a[v[code[u]][j]].second)){
                us[v[code[u]][j]] = 1;
                ans[v[code[u]][j]] = min(ans[v[code[u]][j]], cnt);
            }
        }
        cnt++;
    }
    for (int i = 0; i < q; i++){
        cout << min(m,ans[i]) << "\n";
    }
}

Compilation message (stderr)

pictionary.cpp: In function 'int32_t main()':
pictionary.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[code[u]].size(); j++){
                         ~~^~~~~~~~~~~~~~~~~~~

• 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