Submission #577387

#	Time	Username	Problem	Language	Result	Execution time	Memory
577387		Ronin13	Zamjene (COCI16_zamjene)	C++14	0 / 140	1822 ms	120864 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 = 100000002181;
const ll mod1 = 100000003787;
ll pr1 = 1003019;
ll pr = 1001797;
const int NMAX = 1e6 + 5;
map<pll, ll> mp;
ll par[NMAX];
ll p[NMAX];
ll po[NMAX][2];
ll a[NMAX][2];
ll b[NMAX][2];
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][0] += po[p[v]][0];
    b[v][0] += po[q[v]][0];
    a[v][1] += po[p[v]][1];
    b[v][1] += po[q[v]][1];
    if(a[v][0] != b[v][0] || a[v][1] != b[v][1]) bad++;
    if(b[v][0] != a[v][0] || b[v][1] != a[v][1])curans += mp[{b[v][0] - a[v][0], b[v][1] - a[v][1]}];
    mp[{a[v][0] - b[v][0], a[v][1] - b[v][1]}]++;
}

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

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

void add(int x){
    if(b[x][1] != a[x][1] || b[x][0] != a[x][0] )curans += mp[{b[x][0] - a[x][0], b[x][1] - a[x][1]}] * sz[x];
    mp[{a[x][0] - b[x][0], a[x][1] - b[x][1]}] += 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][0] != b[x][0] || a[x][1] != b[x][1]) bad--;
    if(a[y][0] != b[y][0] || a[y][1] != b[y][1]) bad--;
    rem(x);
    rem(y);
    a[x][0] -= po[p[u]][0];
    a[y][0] -= po[p[v]][0];
    a[x][1] -= po[p[u]][1];
    a[y][1] -= po[p[v]][1];
    a[y][0] += po[p[u]][0];
    a[x][0] += po[p[v]][0];
    a[y][1] += po[p[u]][1];
    a[x][1] += po[p[v]][1];
    a[x][0] %= mod; a[x][0] += mod; a[x][0] %= mod;
    a[y][0] %= mod; a[y][0] += mod; a[y][0] %= mod;
     a[x][1] %= mod1; a[x][1] += mod1; a[x][1] %= mod1;
    a[y][1] %= mod1; a[y][1] += mod1; a[y][1] %= mod1;
    add(x);
    add(y);
    if(a[x][0] != b[x][0] || a[x][1] != b[x][1]) bad++;
    if(a[y][0] != b[y][0] || a[y][1] != b[y][1]) bad++;
}

void add_edge(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(a[u][0] != b[u][0] || a[u][1] != b[u][1]) bad--;
    if(a[v][0] != b[v][0] || b[v][1] != a[v][1]) 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][0] += a[v][0]; a[u][0] %= mod;
    a[u][1] += a[v][1]; a[u][1] %= mod1;
    b[u][1] += b[v][1]; b[u][1] %= mod1;
    b[u][0] += b[v][0]; b[u][0] %= mod;
    if(a[u][0] != b[u][0] || a[u][1] != b[u][1]) bad++;
    add(u);
}

int main(){
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int m; cin >> m;
    po[0][0] = po[0][1] = 1;
    for(int i = 1; i < NMAX; i++) po[i][0] = po[i - 1][0] * pr % mod, po[i][1] = po[i - 1][1] * pr1 % mod1;
    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