Submission #483477

#	Time	Username	Problem	Language	Result	Execution time	Memory
483477		Habitus	Zamjene (COCI16_zamjene)	C++14	0 / 140	6076 ms	141364 KiB

zamjene

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn=(int)1e6+2;
const ll mod=(ll)1e9+7LL;
const int k=(ll)1e4+7LL;

int n, q, p[maxn], kon[maxn], rod[maxn], h[maxn];
ll hes[maxn], hesk[maxn];
ll hesd[maxn], heskd[maxn];
set<int> s;
map<ll, set<int>> cnt;
int par(int x) {
    if(rod[x]==x) return x;
    return rod[x]=par(rod[x]);
}
void merg(int a, int b) {
    a=par(a);
    b=par(b);
    if(a!=b) {
        if(h[a]<h[b]) swap(a, b);
        rod[b]=a;
        h[a]+=h[b];
        cnt[hesd[a]-heskd[a]].erase(a);
        hesd[a]=((hesd[a]+hesd[b])%mod+mod)%mod;
        heskd[a]=((heskd[a]+heskd[b])%mod+mod)%mod;
        cnt[hesd[a]-heskd[a]].insert(a);
        s.erase(b);
    }
}
ll step(ll x, int y) {
    if(y==0) return 1LL;
    if(y==1) return x;
    ll pola=step(x, y/2);
    if(y&1) return ((pola*pola)%mod*x)%mod;
    return (pola*pola)%mod;
}
int main() {
    ios;
    cin >> n >> q;
    for(int i=1; i<=n; ++i) {
        cin >> p[i];
        rod[i]=i;
        h[i]=1;
        hes[i]=hesd[i]=step(p[i], k);
        kon[i]=p[i];
        s.insert(i);
    }
    sort(kon+1, kon+1+n);
    for(int i=1; i<=n; ++i) {
        hesk[i]=heskd[i]=step(kon[i], k);
        cnt[hesd[i]-heskd[i]].insert(i);
    }
    while(q--) {
        int t; cin >> t;
        if(t<3) {
            int x, y; cin >> x >> y;
            if(t==1) {
                int x1=par(x);
                int y1=par(y);
                if(x1!=y1) {
                    cnt[hesd[x1]-heskd[x1]].erase(x1);
                    hesd[x1]-=hes[x];
                    hesd[x1]+=hes[y];
                    hesd[x1]=(hesd[x1]%mod+mod)%mod;
                    cnt[hesd[x1]-heskd[x1]].insert(x1);
                    cnt[hesd[y1]-heskd[y1]].erase(y1);
                    hesd[y1]-=hes[y];
                    hesd[y1]+=hes[x];
                    hesd[y1]=(hesd[y1]%mod+mod)%mod;
                    cnt[hesd[y1]-heskd[y1]].insert(y1);
                    swap(hes[x], hes[y]);
                }
            }
            else {
                merg(x, y);
            }
        }
        else if(t==3) {
            bool moze=1;
            for(auto x:s) {
                if(hesd[x]!=heskd[x]) {
                    moze=0;
                    break;
                }
            }
            if(moze) cout << "DA\n";
            else cout << "NE\n";
        }
        else {
            ll br=0LL;
            for(auto x:s) {
                if(hesd[x]==heskd[x]) continue;
                for(auto y:cnt[-hesd[x]+heskd[x]]) {
                    br+=h[x]*h[y];
                }
            }
            cout << br/2 << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14