Submission #770981

#	Time	Username	Problem	Language	Result	Execution time	Memory
770981		bgnbvnbv	Zamjene (COCI16_zamjene)	C++14	140 / 140	3920 ms	192276 KiB

zamjene

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e6+10;
const ll mod=(1ll<<61)-1;
const ll base=15485863;
ll cnt=0,pw[maxN];
ll lab[maxN];
map<ll,ll> mp;
void ers(ll x,ll v)
{
    if(x!=0) cnt-=v*mp[mod-x];
    mp[x]-=v;
}
void add(ll x,ll v)
{
    if(x!=0) cnt+=v*mp[mod-x];
    mp[x]+=v;
}
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
ll tplt;
ll val[maxN];
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v)
    {
        return;
    }
    tplt--;
    if(lab[u]>lab[v]) swap(u,v);
    ers(val[u],-lab[u]);
    ers(val[v],-lab[v]);
    val[u]+=val[v];
    val[u]%=mod;
    lab[u]+=lab[v];
    lab[v]=u;
    add(val[u],-lab[u]);
}
ll n,t,p[maxN],q[maxN];
void solve()
{
    cin >> n >> t;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i];
        q[i]=p[i];
    }
    pw[0]=1;
    for(int i=1;i<maxN;i++) pw[i]=pw[i-1]*base%mod;
    sort(q+1,q+n+1);
    tplt=n;
    for(int i=1;i<=n;i++)
    {
        lab[i]=-1;
        val[i]=pw[p[i]]-pw[q[i]];
        val[i]%=mod;
        if(val[i]<0) val[i]+=mod;
        add(val[i],-lab[i]);
    }
    ll ct=0;
    for(int cc=1;cc<=t;cc++)
    {
        ll x;
        cin >> x;
        if(x==1)
        {
            ll a,b;
            cin >> a >> b;
            ll i,j;
            i=a;
            j=b;
            a=findset(a);
            b=findset(b);
            if(a==b) {swap(p[i],p[j]);continue;}
            ers(val[a],-lab[a]);
            ers(val[b],-lab[b]);
            val[a]-=pw[p[i]]-pw[p[j]];
            val[b]-=pw[p[j]]-pw[p[i]];
            val[a]%=mod;
            val[b]%=mod;
            if(val[a]<0) val[a]+=mod;
            if(val[b]<0) val[b]+=mod;
            add(val[a],-lab[a]);
            add(val[b],-lab[b]);
            swap(p[j],p[i]);
        }
        else if(x==2)
        {
            ll a,b;
            cin >> a >> b;
            unite(a,b);
        }
        else if(x==4)
        {
            cout << cnt << '\n';
           // ct++;
        }
        else
        {
           // ct++;
            if(mp[0]==n) cout <<"DA\n";
            else cout <<"NE\n";
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

zamjene.cpp: In function 'void solve()':
zamjene.cpp:71:8: warning: unused variable 'ct' [-Wunused-variable]
   71 |     ll ct=0;
      |        ^~

• 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