제출 #770981

#제출 시각아이디문제언어결과실행 시간메모리
770981bgnbvnbvZamjene (COCI16_zamjene)C++14
140 / 140
3920 ms192276 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=1e6+10; const ll mod=(1ll<<61)-1; const ll base=15485863; ll cnt=0,pw[maxN]; ll lab[maxN]; map<ll,ll> mp; void ers(ll x,ll v) { if(x!=0) cnt-=v*mp[mod-x]; mp[x]-=v; } void add(ll x,ll v) { if(x!=0) cnt+=v*mp[mod-x]; mp[x]+=v; } ll findset(ll x) { return lab[x]<0?x:lab[x]=findset(lab[x]); } ll tplt; ll val[maxN]; void unite(ll u,ll v) { u=findset(u); v=findset(v); if(u==v) { return; } tplt--; if(lab[u]>lab[v]) swap(u,v); ers(val[u],-lab[u]); ers(val[v],-lab[v]); val[u]+=val[v]; val[u]%=mod; lab[u]+=lab[v]; lab[v]=u; add(val[u],-lab[u]); } ll n,t,p[maxN],q[maxN]; void solve() { cin >> n >> t; for(int i=1;i<=n;i++) { cin >> p[i]; q[i]=p[i]; } pw[0]=1; for(int i=1;i<maxN;i++) pw[i]=pw[i-1]*base%mod; sort(q+1,q+n+1); tplt=n; for(int i=1;i<=n;i++) { lab[i]=-1; val[i]=pw[p[i]]-pw[q[i]]; val[i]%=mod; if(val[i]<0) val[i]+=mod; add(val[i],-lab[i]); } ll ct=0; for(int cc=1;cc<=t;cc++) { ll x; cin >> x; if(x==1) { ll a,b; cin >> a >> b; ll i,j; i=a; j=b; a=findset(a); b=findset(b); if(a==b) {swap(p[i],p[j]);continue;} ers(val[a],-lab[a]); ers(val[b],-lab[b]); val[a]-=pw[p[i]]-pw[p[j]]; val[b]-=pw[p[j]]-pw[p[i]]; val[a]%=mod; val[b]%=mod; if(val[a]<0) val[a]+=mod; if(val[b]<0) val[b]+=mod; add(val[a],-lab[a]); add(val[b],-lab[b]); swap(p[j],p[i]); } else if(x==2) { ll a,b; cin >> a >> b; unite(a,b); } else if(x==4) { cout << cnt << '\n'; // ct++; } else { // ct++; if(mp[0]==n) cout <<"DA\n"; else cout <<"NE\n"; } } } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

컴파일 시 표준 에러 (stderr) 메시지

zamjene.cpp: In function 'void solve()':
zamjene.cpp:71:8: warning: unused variable 'ct' [-Wunused-variable]
   71 |     ll ct=0;
      |        ^~
#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...