oj.uz

Submission #483477

# Submission time Handle Problem Language Result Execution time Memory
483477 2021-10-29T20:41:04 Z Habitus Zamjene (COCI16_zamjene) C++14
0 / 140
 6000 ms 141364 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 hesd[maxn], heskd[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[hesd[a]-heskd[a]].erase(a);
        hesd[a]=((hesd[a]+hesd[b])%mod+mod)%mod;
        heskd[a]=((heskd[a]+heskd[b])%mod+mod)%mod;
        cnt[hesd[a]-heskd[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]=hesd[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]=heskd[i]=step(kon[i], k);
        cnt[hesd[i]-heskd[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[hesd[x1]-heskd[x1]].erase(x1);
                    hesd[x1]-=hes[x];
                    hesd[x1]+=hes[y];
                    hesd[x1]=(hesd[x1]%mod+mod)%mod;
                    cnt[hesd[x1]-heskd[x1]].insert(x1);
                    cnt[hesd[y1]-heskd[y1]].erase(y1);
                    hesd[y1]-=hes[y];
                    hesd[y1]+=hes[x];
                    hesd[y1]=(hesd[y1]%mod+mod)%mod;
                    cnt[hesd[y1]-heskd[y1]].insert(y1);
                    swap(hes[x], hes[y]);
                }
            }
            else {
                merg(x, y);
            }
        }
        else if(t==3) {
            bool moze=1;
            for(auto x:s) {
                if(hesd[x]!=heskd[x]) {
                    moze=0;
                    break;
                }
            }
            if(moze) cout << "DA\n";
            else cout << "NE\n";
        }
        else {
            ll br=0LL;
            for(auto x:s) {
                if(hesd[x]==heskd[x]) continue;
                for(auto y:cnt[-hesd[x]+heskd[x]]) {
                    br+=h[x]*h[y];
                }
            }
            cout << br/2 << "\n";
        }
    }
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 985 ms 1804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6040 ms 14404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6043 ms 70784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6067 ms 141364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6076 ms 141124 KB Time limit exceeded
2 Halted 0 ms 0 KB -