oj.uz

Submission #1073378

# Submission time Handle Problem Language Result Execution time Memory
1073378 2024-08-24T13:47:55 Z beaconmc Pictionary (COCI18_pictionary) C++14
140 / 140
 488 ms 63224 KB 
#include <bits/stdc++.h>

typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

const ll maxn = 100005;
set<vector<ll>> req[maxn];
set<ll> has[maxn];

map<ll,ll> opps;


ll cmp[maxn];

ll find(ll a){
    while (a != cmp[a]){
        cmp[a] = cmp[cmp[a]];
        a = cmp[a];
    }
    return a;
}
map<vector<ll>, ll> ans;

void unite(ll a, ll b, ll k){
    if (find(a) == find(b)) return;
    ll A = find(a);
    ll B = find(b);
    if (req[B].size() > req[A].size()){
        swap(A, B);
    }
    vector<vector<ll>> used;
    for (auto&i : req[B]){
        if (has[A].count(i[0])){

            ans[{i[0], i[1]}] = k;
            used.push_back(i);
        }
    }
    for (auto&i : used) req[B].erase(i);
    for (auto&i : used) reverse(i.begin(), i.end());
    for (auto&i : used) req[A].erase(i);

    if (has[A].size() > has[B].size()) swap(has[A], has[B]);
    for (auto&i : has[A]){
        has[B].insert(i);
    }

    if (req[A].size() > req[B].size()) swap(req[A], req[B]);
    for (auto&i : req[A]){
        req[B].insert(i);
    }
    cmp[A] = B;
}
int main(){
    FOR(i,0,maxn) cmp[i] = i;
    ll n,m,q;
    cin >> n >> m >> q;
    vector<vector<ll>> queries;
    FOR(i,0,q){
        ll a,b;
        cin >> a >> b;
        queries.push_back({a,b});
        req[b].insert({a, b});
        req[a].insert({b,a});
    }
    FOR(i,1,n+1) has[i].insert(i);
    FORNEG(i, m, 0){

        ll cur = i;
        while (cur+i <= n){
            unite(cur, cur+i, i);
            cur+=i;
        }
    }
    for (auto&i : queries){
        if (ans.count(i)) cout << m-ans[i]+1 << "\n";
        else{
            reverse(i.begin(), i.end());
            cout << m-ans[i]+1 << "\n";
        }
        
    }


}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12888 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18956 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 42916 KB Output is correct
2 Correct 239 ms 36092 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 57852 KB Output is correct
2 Correct 340 ms 49664 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 31236 KB Output is correct
2 Correct 136 ms 30724 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 33540 KB Output is correct
2 Correct 194 ms 30940 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 42748 KB Output is correct
2 Correct 166 ms 34704 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 41472 KB Output is correct
2 Correct 335 ms 52544 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 56060 KB Output is correct
2 Correct 396 ms 56320 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 63224 KB Output is correct
2 Correct 488 ms 61824 KB Output is correct