# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
483476 |
2021-10-29T20:30:15 Z |
Habitus |
Zamjene (COCI16_zamjene) |
C++14 |
|
6000 ms |
136468 KB |
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn=(int)1e6+2;
const ll mod=(ll)1e9+7LL;
const int k=(ll)1e4+7LL;
int n, q, p[maxn], kon[maxn], rod[maxn], h[maxn];
ll hes[maxn], hesk[maxn];
ll hd[maxn];
set<int> s;
map<ll, set<int>> cnt;
int par(int x) {
if(rod[x]==x) return x;
return rod[x]=par(rod[x]);
}
void merg(int a, int b) {
a=par(a);
b=par(b);
if(a!=b) {
if(h[a]<h[b]) swap(a, b);
rod[b]=a;
h[a]+=h[b];
cnt[hd[a]].erase(a);
hd[a]=hd[a]+hd[b];
cnt[hd[a]].insert(a);
s.erase(b);
}
}
ll step(ll x, int y) {
if(y==0) return 1LL;
if(y==1) return x;
ll pola=step(x, y/2);
if(y&1) return ((pola*pola)%mod*x)%mod;
return (pola*pola)%mod;
}
int main() {
ios;
cin >> n >> q;
for(int i=1; i<=n; ++i) {
cin >> p[i];
rod[i]=i;
h[i]=1;
hes[i]=step(p[i], k);
kon[i]=p[i];
s.insert(i);
}
sort(kon+1, kon+1+n);
for(int i=1; i<=n; ++i) {
hesk[i]=step(kon[i], k);
hd[i]=hes[i]-hesk[i];
cnt[hd[i]].insert(i);
}
while(q--) {
int t; cin >> t;
if(t<3) {
int x, y; cin >> x >> y;
if(t==1) {
int x1=par(x);
int y1=par(y);
if(x1!=y1) {
cnt[hd[x1]].erase(x1);
hd[x1]-=hes[x];
hd[x1]+=hes[y];
//hd[x1]=(hd[x1]%mod+mod)%mod;
cnt[hd[x1]].insert(x1);
cnt[hd[y1]].erase(y1);
hd[y1]-=hes[y];
hd[y1]+=hes[x];
swap(hes[x], hes[y]);
//hd[y1]=(hd[y1]%mod+mod)%mod;
cnt[hd[y1]].insert(y1);
}
}
else {
merg(x, y);
}
}
else if(t==3) {
bool moze=1;
for(auto x:s) {
if(hd[x]!=0LL) {
moze=0;
break;
}
}
if(moze) cout << "DA\n";
else cout << "NE\n";
}
else {
ll br=0LL;
for(auto x:s) {
if(hd[x]==0LL) continue;
for(auto y:cnt[-hd[x]]) {
br+=h[x]*h[y];
}
}
cout << br/2 << "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
84 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1006 ms |
1960 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6062 ms |
13912 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6087 ms |
68036 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6091 ms |
136468 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6095 ms |
135724 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |