Submission #577287

#	Time	Username	Problem	Language	Result	Execution time	Memory
577287		Ronin13	Zamjene (COCI16_zamjene)	C++14	0 / 140	2166 ms	97616 KiB

zamjene

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const ll mod = 1e9 + 7;
ll pr = 1000003;
const int NMAX = 1e6 + 1;
map<ll, ll> mp;
ll par[NMAX];
ll p[NMAX];
ll po[NMAX];
ll a[NMAX];
ll b[NMAX];
ll q[NMAX];
ll sz[NMAX];
int bad = 0;
ll curans = 0;
void make_set(int v){
    par[v] = v;
    sz[v] = 1;
    a[v] += po[p[v]];
    b[v] += po[q[v]];
    if(a[v] != b[v]) bad++;
    if(b[v] != a[v])curans += mp[b[v] - a[v]];
    mp[a[v] - b[v]]++;
}

int find_set(int v){
    return v == par[v] ? par[v] : par[v] = find_set(par[v]);
}

void rem(int x){
    if(b[x] != a[x])curans -= mp[b[x] - a[x]] * sz[x];
    mp[a[x] - b[x]] -= sz[x];
}

void add(int x){

    if(b[x] != a[x])curans += mp[b[x] - a[x]] * sz[x];
    mp[a[x] - b[x]] += sz[x];
}

void swp(int u, int v){
    int x = find_set(u);
    int y = find_set(v);
    if(x == y) return;
    if(a[x] != b[x]) bad--;
    if(a[y] != b[y]) bad--;
    rem(x);
    rem(y);
    a[x] -= po[p[u]];
    a[y] -= po[p[v]];
    a[x] += po[p[v]];
    a[y] += po[p[u]];
    a[x] %= mod; a[x] += mod; a[x] %= mod;
    a[y] %= mod; a[y] += mod; a[y] %= mod;
    add(x);
    add(y);
    if(a[x] != b[x]) bad++;
    if(a[y] != b[y]) bad++;
}

void add_edge(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(a[u] != b[u]) bad--;
    if(a[v] != b[v]) bad--;
    rem(u);
    rem(v);
    //cout << curans << "\n";
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    a[u] += a[v]; a[u] %= mod;
    b[u] += b[v]; b[u] %= mod;
    if(a[u] != b[u]) bad++;
    add(u);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int m; cin >> m;
    po[0] = 1;
    for(int i = 1; i < NMAX; i++) po[i] = po[i - 1] * pr % mod;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        q[i] = p[i];
    }
    sort(q + 1, q + 1  + n);
    for(int i = 1; i <= n; i++) make_set(i);
    while(m--){
        int type; cin >> type;
        if(type == 1){
            int u, v; cin >> u >> v;
            swp(u, v);
            swap(p[u], p[v]);
        }
        if(type == 2){
            int u, v; cin >> u >> v;
            add_edge(u, v);
        }
        if(type == 3){
            if(bad == 0) cout << "DA\n";
            else cout << "NE\n";
        }
        if(type == 4){
            cout << curans << "\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