oj.uz

Submission #577287

# Submission time Handle Problem Language Result Execution time Memory
577287 2022-06-14T12:25:10 Z Ronin13 Zamjene (COCI16_zamjene) C++14
0 / 140
 2166 ms 97616 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8112 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Incorrect 9 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8148 KB Output is correct
2 Incorrect 9 ms 8192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8148 KB Output is correct
2 Incorrect 9 ms 8220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8148 KB Output is correct
2 Incorrect 10 ms 8276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 13536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1235 ms 49372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2166 ms 97616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1045 ms 63704 KB Output isn't correct
2 Halted 0 ms 0 KB -