Submission #1073375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073375		beaconmc	Pictionary (COCI18_pictionary)	C++17	140 / 140	473 ms	63224 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14