oj.uz

Submission #165642

# Submission time Handle Problem Language Result Execution time Memory
165642 2019-11-28T03:47:53 Z _qVp_ Zamjene (COCI16_zamjene) C++14
126 / 140
 6000 ms 181652 KB 
#include <bits/stdc++.h>

using namespace std;

const int base = 1234577;
const int md = 1e6 + 10;

int n, T;
int p[md], q[md], sz[md], lab[md];
long long pw[md], id[md], val[md];
long long pairs;
map < long long, int > diff_nodes; 

void addNode(int sign, long long diff, int num) {
    if (diff != 0) 
        pairs += sign * num * diff_nodes[-diff];
    diff_nodes[diff] += sign * num;
}

int root(int x) {
    if (lab[x] < 0)
        return x;
    return lab[x] = root(lab[x]);
}

void init() {
    scanf("%d %d", &n, &T);
    pw[0] = 1;
    for(int i = 1; i < md; i++)
        pw[i] = pw[i - 1] * base;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        q[i] = p[i];
        lab[i] = -1;
        sz[i] = 1;
    }
    sort(q + 1, q + 1 + n);
    for(int i = 1; i <= n; i++) {
        id[i] = pw[q[i]];
        val[i] = pw[p[i]];
        //cout << id[i] << " " << val[i] << endl;
        addNode(1, id[i] - val[i], sz[i]);
    }
}

void add(int sign, int ru, int u, int v) {
    id[ru] += sign * pw[u];
    val[ru] += sign * pw[v];
    sz[ru] += sign; 
}

void merges(int u, int v) {
    int ru = root(u), rv = root(v);
    if (ru == rv)
        return ;
    if (lab[ru] > lab[rv]) 
        swap(ru, rv);
    addNode(-1, id[ru] - val[ru], sz[ru]);
    addNode(-1, id[rv] - val[rv], sz[rv]);
    lab[ru] += lab[rv];
    lab[rv] = ru;
    sz[ru] += sz[rv];
    id[ru] += id[rv];
    val[ru] += val[rv];
    //cout << id[ru] << " " << val[ru] << endl;
    addNode(1, id[ru] - val[ru], sz[ru]);
}

int main() {
    //freopen("test.in", "r", stdin);
    //ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    while (T--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int u, v;
            scanf("%d %d", &u, &v);
            int ru = root(u), rv = root(v);
            if (ru == rv) {
                swap(p[u], p[v]);
                continue;
            }
            addNode(-1, id[ru] - val[ru], sz[ru]);
            addNode(-1, id[rv] - val[rv], sz[rv]);
            add(-1, ru, u, p[u]);
            add(-1, rv, v, p[v]);

            swap(p[u], p[v]);

            add(1, ru, u, p[u]);
            add(1, rv, v, p[v]);
            addNode(1, id[ru] - val[ru], sz[ru]);
            addNode(1, id[rv] - val[rv], sz[rv]);
        } else if (type == 2) {
            int u, v;
            scanf("%d %d", &u, &v);
            merges(u, v);
        } else if (type == 3) {
            //cout << diff_nodes[0]  << endl;
            if (diff_nodes[0] == n)
                printf("DA\n");
            else printf("NE\n");
        } else {
            printf("%lld\n", pairs);
        }
    }
    return 0;
}

Compilation message

zamjene.cpp: In function 'void init()':
zamjene.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &T);
     ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &type);
         ~~~~~^~~~~~~~~~~~~
zamjene.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 12 ms 8312 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 10 ms 8312 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8232 KB Output is correct
3 Correct 9 ms 8312 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct
3 Correct 10 ms 8312 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8568 KB Output is correct
2 Correct 17 ms 8568 KB Output is correct
3 Correct 18 ms 8696 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 11780 KB Output is correct
2 Correct 143 ms 13432 KB Output is correct
3 Correct 223 ms 16504 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 40108 KB Output is correct
2 Correct 5622 ms 130664 KB Output is correct
3 Execution timed out 6090 ms 181652 KB Time limit exceeded

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2958 ms 81320 KB Output is correct
2 Correct 5054 ms 102268 KB Output is correct
3 Correct 2342 ms 90092 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 47060 KB Output is correct
2 Correct 3442 ms 86328 KB Output is correct
3 Correct 2259 ms 90104 KB Output is correct