Kod źródłowy zgłoszenia nr 922960

#include <bits/stdc++.h>
using namespace std;struct H{static uint64_t s(uint64_t x){x+=0x9e3779b97f4a7c15ULL;x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;x=(x^(x>>27))*0x94d049bb133111ebULL;return x^(x>>31);}size_t operator()(uint64_t x)const{static const uint64_t r=chrono::steady_clock::now().time_since_epoch().count();return s(x+r);}};struct D{vector<int>p,z;D(){}D(int n):p(n),z(n,1){iota(p.begin(),p.end(),0);}int f(int x){while(p[x]!=x)p[x]=p[p[x]],x=p[x];return x;}bool u(int a,int b){a=f(a);b=f(b);if(a==b)return 0;if(z[a]<z[b])swap(a,b);p[b]=a;z[a]+=z[b];return 1;}};int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while(T--){int n,m,k;cin>>n>>m>>k;vector<int>a(n);for(int&i:a)cin>>i;vector<pair<int,int>>e;e.reserve(m);D d(n);for(int i=0,u,v;i<m;i++){cin>>u>>v;--u;--v;e.push_back({u,v});if(a[u]==a[v])d.u(u,v);}vector<int>r(n,-1),b(n),c;vector<vector<int>>h(k+1);int N=0;for(int i=0;i<n;i++){int x=d.f(i);if(r[x]==-1){r[x]=N++;c.push_back(a[i]);h[a[i]].push_back(r[x]);}b[i]=r[x];}vector<vector<int>>g(N);for(auto[u,v]:e){u=b[u];v=b[v];if(u==v)continue;g[u].push_back(v);g[v].push_back(u);}vector<int>w(k+1);vector<char>A(k+1),I(k+1);queue<int>q;int p=0;for(int i=1;i<=k;i++){w[i]=h[i].size();if(w[i]){p++;if(w[i]==1)q.push(i),I[i]=1;}}vector<int>pc(N),z(N,1);iota(pc.begin(),pc.end(),0);auto F=[&](int x){while(pc[x]!=x)pc[x]=pc[pc[x]],x=pc[x];return x;};vector<int>pa(N),s(N,1);iota(pa.begin(),pa.end(),0);vector<char>P(N);using M=unordered_map<int,int,H>;vector<M>mp(N);auto G=[&](int x){while(pa[x]!=x)pa[x]=pa[pa[x]],x=pa[x];return x;};function<int(int,int)>C=[&](int x,int y){x=F(x);y=F(y);if(x==y)return x;int t=c[x];if(z[x]<z[y])swap(x,y);pc[y]=x;z[x]+=z[y];if(--w[t]==1&&!A[t]&&!I[t])q.push(t),I[t]=1;return x;};function<int(int,int)>U=[&](int a,int b){a=G(a);b=G(b);if(a==b)return a;if(mp[a].size()<mp[b].size()||(mp[a].size()==mp[b].size()&&s[a]<s[b]))swap(a,b);pa[b]=a;s[a]+=s[b];for(auto&[t,v]:mp[b]){if(A[t])continue;v=F(v);auto it=mp[a].find(t);if(it==mp[a].end())mp[a][t]=v;else{int u=F(it->second);it->second=u!=v?C(u,v):u;}}mp[b].clear();return a;};auto S=[&](int r,int t,int v){if(A[t])return;r=G(r);v=F(v);auto it=mp[r].find(t);if(it==mp[r].end())mp[r][t]=v;else{int u=F(it->second);it->second=u!=v?C(u,v):u;}};int o=0;while(!q.empty()){int t=q.front();q.pop();if(A[t])continue;A[t]=1;o++;for(int v:h[t])P[v]=1,pa[v]=v,s[v]=1,mp[v].clear();for(int v:h[t])for(int u:g[v])if(P[u])U(v,u);for(int v:h[t]){int r=G(v);for(int u:g[v])if(!P[u])S(r,c[u],u);}}cout<<(o==p?"TAK\n":"NIE\n");}}

1
2

#include <bits/stdc++.h>
using namespace std;struct H{static uint64_t s(uint64_t x){x+=0x9e3779b97f4a7c15ULL;x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;x=(x^(x>>27))*0x94d049bb133111ebULL;return x^(x>>31);}size_t operator()(uint64_t x)const{static const uint64_t r=chrono::steady_clock::now().time_since_epoch().count();return s(x+r);}};struct D{vector<int>p,z;D(){}D(int n):p(n),z(n,1){iota(p.begin(),p.end(),0);}int f(int x){while(p[x]!=x)p[x]=p[p[x]],x=p[x];return x;}bool u(int a,int b){a=f(a);b=f(b);if(a==b)return 0;if(z[a]<z[b])swap(a,b);p[b]=a;z[a]+=z[b];return 1;}};int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while(T--){int n,m,k;cin>>n>>m>>k;vector<int>a(n);for(int&i:a)cin>>i;vector<pair<int,int>>e;e.reserve(m);D d(n);for(int i=0,u,v;i<m;i++){cin>>u>>v;--u;--v;e.push_back({u,v});if(a[u]==a[v])d.u(u,v);}vector<int>r(n,-1),b(n),c;vector<vector<int>>h(k+1);int N=0;for(int i=0;i<n;i++){int x=d.f(i);if(r[x]==-1){r[x]=N++;c.push_back(a[i]);h[a[i]].push_back(r[x]);}b[i]=r[x];}vector<vector<int>>g(N);for(auto[u,v]:e){u=b[u];v=b[v];if(u==v)continue;g[u].push_back(v);g[v].push_back(u);}vector<int>w(k+1);vector<char>A(k+1),I(k+1);queue<int>q;int p=0;for(int i=1;i<=k;i++){w[i]=h[i].size();if(w[i]){p++;if(w[i]==1)q.push(i),I[i]=1;}}vector<int>pc(N),z(N,1);iota(pc.begin(),pc.end(),0);auto F=[&](int x){while(pc[x]!=x)pc[x]=pc[pc[x]],x=pc[x];return x;};vector<int>pa(N),s(N,1);iota(pa.begin(),pa.end(),0);vector<char>P(N);using M=unordered_map<int,int,H>;vector<M>mp(N);auto G=[&](int x){while(pa[x]!=x)pa[x]=pa[pa[x]],x=pa[x];return x;};function<int(int,int)>C=[&](int x,int y){x=F(x);y=F(y);if(x==y)return x;int t=c[x];if(z[x]<z[y])swap(x,y);pc[y]=x;z[x]+=z[y];if(--w[t]==1&&!A[t]&&!I[t])q.push(t),I[t]=1;return x;};function<int(int,int)>U=[&](int a,int b){a=G(a);b=G(b);if(a==b)return a;if(mp[a].size()<mp[b].size()||(mp[a].size()==mp[b].size()&&s[a]<s[b]))swap(a,b);pa[b]=a;s[a]+=s[b];for(auto&[t,v]:mp[b]){if(A[t])continue;v=F(v);auto it=mp[a].find(t);if(it==mp[a].end())mp[a][t]=v;else{int u=F(it->second);it->second=u!=v?C(u,v):u;}}mp[b].clear();return a;};auto S=[&](int r,int t,int v){if(A[t])return;r=G(r);v=F(v);auto it=mp[r].find(t);if(it==mp[r].end())mp[r][t]=v;else{int u=F(it->second);it->second=u!=v?C(u,v):u;}};int o=0;while(!q.empty()){int t=q.front();q.pop();if(A[t])continue;A[t]=1;o++;for(int v:h[t])P[v]=1,pa[v]=v,s[v]=1,mp[v].clear();for(int v:h[t])for(int u:g[v])if(P[u])U(v,u);for(int v:h[t]){int r=G(v);for(int u:g[v])if(!P[u])S(r,c[u],u);}}cout<<(o==p?"TAK\n":"NIE\n");}}