Submission #165651

#TimeUsernameProblemLanguageResultExecution timeMemory
165651_qVp_Zamjene (COCI16_zamjene)C++14
56 / 140
5963 ms182540 KiB
#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 { 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) {
                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...