oj.uz

Submission #1073375

# Submission time Handle Problem Language Result Execution time Memory
1073375 2024-08-24T13:45:53 Z beaconmc Pictionary (COCI18_pictionary) C++17
140 / 140
 473 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 18952 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 42752 KB Output is correct
2 Correct 250 ms 36116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 58244 KB Output is correct
2 Correct 347 ms 50432 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 31124 KB Output is correct
2 Correct 150 ms 30724 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 33540 KB Output is correct
2 Correct 185 ms 31052 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 44288 KB Output is correct
2 Correct 170 ms 34536 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 41488 KB Output is correct
2 Correct 341 ms 51448 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 55920 KB Output is correct
2 Correct 408 ms 56124 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 63224 KB Output is correct
2 Correct 473 ms 61944 KB Output is correct