| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 209114 |
2020-03-13T08:36:38 Z |
Sensei |
Zamjene (COCI16_zamjene) |
C++14 |
|
1425 ms |
85224 KB |
/*
DATE: 2020-03-13 10:51:02
NAME:
PROBLEM: COCI16_ZAMJENE
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
const long long MOD = 1e9 + 7;
const int prime = 67;
long long add(long long x, long long y) {
return ((x % MOD) + (y % MOD)) % MOD;
}
long long sub(long long x, long long y) {
return ((x % MOD) + MOD - (y % MOD)) % MOD;
}
long long mul(long long x, long long y) {
return ((x % MOD) * (y % MOD)) % MOD;
}
long long liftt[MAXN + 7];
long long lift(int x) {
return liftt[x];
}
int p[MAXN + 7];
int q[MAXN + 7];
int par[MAXN + 7];
int r[MAXN + 7];
long long P[MAXN + 7];
long long Q[MAXN + 7];
unordered_map<long long, int> cnt;
long long ans_for_4 = 0;
void ins(int x, int y) {
// cerr << "ins: " << x << " " << y << " " << p[y] << "\n";
long long t = sub(P[x], Q[x]);
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[t]--;
P[x] = add(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += cnt[sub(0, t)];
}
cnt[t]++;
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
}
void del(int x, int y) {
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[t]--;
P[x] = sub(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += cnt[sub(0, t)];
}
cnt[t]++;
}
void makeset(int x) {
par[x] = x;
r[x] = 0;
Q[x] = lift(q[x]);
P[x] = 0;
cnt[sub(P[x], Q[x])]++;
ins(x, x);
}
int findset(int x) {
if (par[x] != x) {
par[x] = findset(par[x]);
}
return par[x];
}
void link(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return;
}
if (r[x] > r[y]) {
par[y] = x;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])]--;
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])]--;
P[x] = add(P[x], P[y]);
Q[x] = add(Q[x], Q[y]);
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])]++;
}
else {
par[x] = y;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])]--;
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])]--;
P[y] = add(P[y], P[x]);
Q[y] = add(Q[y], Q[x]);
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 += cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])]++;
if (r[x] == r[y]) {
r[y]++;
}
}
}
int main() {
liftt[0] = 1;
for (int i = 1; i <= MAXN; i++) {
liftt[i] = mul(liftt[i - 1], prime);
}
int n, qry;
cin >> n >> qry;
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
q[i] = p[i];
}
sort(q + 1, q + n + 1);
for (int i = 1; i <= n; i++) {
makeset(i);
}
int ccnt = n;
while (qry--) {
// for (unordered_map<long long, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
// cerr << it->first << " " << it->second << "\n";
// }
int ty;
scanf("%d", &ty);
if (ty == 1) {
int a, b;
scanf("%d %d", &a, &b);
int x = findset(a);
int y = findset(b);
if (x == y) {
continue;
}
del(x, a);
ins(x, b);
del(y, b);
ins(y, a);
swap(p[a], p[b]);
}
else if (ty == 2) {
int a, b;
scanf("%d %d", &a, &b);
if (findset(a) != findset(b)) {
ccnt--;
}
link(a, b);
}
else if (ty == 3) {
if (cnt[0] == ccnt) {
printf("DA\n");
}
else {
printf("NE\n");
}
}
else if (ty == 4) {
printf("%lld\n", ans_for_4);
}
}
return 0;
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
zamjene.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ty);
~~~~~^~~~~~~~~~~
zamjene.cpp:187:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:202:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
8312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
8696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
12796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1026 ms |
50064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1425 ms |
85224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1034 ms |
57864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
