oj.uz

Submission #1073373

# Submission time Handle Problem Language Result Execution time Memory
1073373 2024-08-24T13:43:53 Z beaconmc Pictionary (COCI18_pictionary) C++17
0 / 140
 495 ms 63744 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 19044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 42752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 402 ms 58368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 31236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 33456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 43516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 42376 KB Output is correct
2 Incorrect 362 ms 51964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 55804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 495 ms 63744 KB Output isn't correct
2 Halted 0 ms 0 KB -