oj.uz

답안 #255245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255245 2020-07-31T16:04:37 Z Vladikus004 Zamjene (COCI16_zamjene) C++14
0 / 140
 2261 ms 98552 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

mt19937_64 rnd(42);
const int N = 1000000 + 3;
int n, q, a[N], p[N], ans_4, ans_3, cnt, b[N], sz[N];
ll code[N], sum[N], nsum[N];
map <ll, int> mp;

void init(){
    for (int i = 0; i < n; i++){
        p[i] = i;
        sum[i] = code[a[i]];
        nsum[i] = code[b[i]];
        sz[i] = 1;
        if (sum[i] == nsum[i]){
            ans_3++;
        }else{
            ans_4 += mp[nsum[i] - sum[i]];
            mp[sum[i] - nsum[i]]++;
        }
    }
}

int get_anc(int x){
    if (x == p[x]) return x;
    return p[x] = get_anc(p[x]);
}

void unite(int x, int y){
    x = get_anc(x);
    y = get_anc(y);
    if (x == y) return;
    cnt--;

    if (sum[x] != nsum[x]){
        ans_4 -= mp[nsum[x] - sum[x]] * sz[x];
        mp[sum[x] - nsum[x]] -= sz[x];
    }else ans_3--;
    if (sum[y] != nsum[y]){
        ans_4 -= mp[nsum[y] - sum[y]] * sz[y];
        mp[sum[y] - nsum[y]] -= sz[y];
    }else ans_3--;

    if (rnd() & 1) swap(x, y);
    nsum[x] += nsum[y];
    sum[x] += sum[y];
    p[y] = x;
    sz[x] += sz[y];

    ans_4 += mp[nsum[x] - sum[x]] * sz[x];
    mp[sum[x] - nsum[x]]+=sz[x];
    if (sum[x] == nsum[x]) ans_3++;
}

void sw(int x, int y){
    int ax = get_anc(x);
    int ay = get_anc(y);
    if (ax == ay) return;

    if (sum[x] != nsum[x]){
        ans_4 -= mp[nsum[x] - sum[x]] * sz[ax];
        mp[sum[x] - nsum[x]]-=sz[ax];
    }else ans_3--;
    if (sum[y] != nsum[y]){
        ans_4 -= mp[nsum[y] - sum[y]] * sz[ay];
        mp[sum[y] - nsum[y]]-=sz[ay];
    }else ans_3--;

    sum[ax] += code[a[y]] - code[a[x]];
    sum[ay] += code[a[x]] - code[a[y]];

    if (sum[x] == nsum[x]) ans_3++;
    else{
        ans_4 += mp[nsum[x] - sum[x]] * sz[ax];
        mp[sum[ax] - nsum[ax]]+=sz[ax];
    }

    if (sum[y] == nsum[y]) ans_3++;
    else{
        ans_4 += mp[nsum[y] - sum[y]] * sz[ay];
        mp[sum[ay] - nsum[ay]]+=sz[ay];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        --a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    for (int i = 0; i < n; i++)
        code[i] = rnd();
    init();
    cnt = n;
    for (int i = 0; i < q; i++){
        int tp, x, y;
        cin >> tp;
        if (tp == 1){
            cin >> x >> y;
            --x; --y;
            sw(x, y);
        }else
        if (tp == 2){
            cin >> x >> y;
            --x; --y;
            unite(x, y);
        }else
        if (tp == 3){
            if (ans_3 == cnt) cout << "DA\n";
            else cout << "NE\n";
        }else{
            cout << ans_4 << "\n";
        }
    }
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 5812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1400 ms 48124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2261 ms 98552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1006 ms 58616 KB Output isn't correct
2 Halted 0 ms 0 KB -