Submission #165653

#	Time	Username	Problem	Language	Result	Execution time	Memory
165653		_qVp_	Zamjene (COCI16_zamjene)	C++14	140 / 140	5688 ms	182784 KiB

zamjene

#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; 

inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    //neg = (c == '-') ? -1 : 1;
    *x = c - '0';
    //readchar();
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c - '0';
    //*x *= neg;
    return 1;
}

void print(long long n) {
    //cout << n << endl;
    if (!n) return ;
    print(n / 10);
    putchar(n % 10 + 48);
}

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() {
    ReadInt(&n); ReadInt(&T);
    //cerr << n << " " << T << endl;
    pw[0] = 1;
    for(int i = 1; i < md; i++)
        pw[i] = pw[i - 1] * base;
    for(int i = 1; i <= n; i++) {
        ReadInt(&p[i]);
       // cerr << p[i] << endl;
        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]];
        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) {
    //cerr << "checking";
    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);
    //freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    init();
    while (T--) {
        int type;
        ReadInt(&type);
        //cerr << "*" << type << endl;
        if (type == 1) {
            int u, v;
            ReadInt(&u); ReadInt(&v);
        //    cerr << u << " " << v << endl;
            int ru = root(u), rv = root(v);
            if (ru == rv) {
                swap(p[u], p[v]);
                continue;
            }
            //cerr << i << endl;
            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;
            ReadInt(&u); ReadInt(&v);
        //    cerr << u <<" " << v << endl;
            merges(u, v);
        } else if (type == 3) {
            if (diff_nodes[0] == n)
                puts("DA");
            else puts("NE");
        } else {
            if (pairs == 0)
                puts("0");
            else {
                print(pairs); puts("");
            }
        }
    }
    return 0;
}

Compilation message (stderr)

zamjene.cpp: In function 'int ReadInt(int*)':
zamjene.cpp:25:20: warning: unused variable 'neg' [-Wunused-variable]
     static char c, neg;
                    ^~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:135:16: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
         } else if (type == 3) {
                ^~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14