oj.uz

Submission #251970

# Submission time Handle Problem Language Result Execution time Memory
251970 2020-07-23T10:00:52 Z Vladikus004 Pictionary (COCI18_pictionary) C++14
0 / 140
 1500 ms 10372 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1728 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 2704 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1581 ms 6560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 8468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 5152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 5148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 7064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 10372 KB Output is correct
2 Execution timed out 1584 ms 8852 KB Time limit exceeded

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 8920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1587 ms 9160 KB Time limit exceeded
2 Halted 0 ms 0 KB -