2021 JNU Competition F
In my last year as an undergraduate, I got a opportunity to be a participant of the XCPC school competition, not a author of the problems or a referee. I thought it has some special meaning for me, so I was exciting and asked my two old teammate to join with me. We had been a team again.
Fortunately, we solved the fifth problem in the last 10 minutes, and finally won the second prize( rank 4 ).
Problem
Given a undirected graph that each node have only one degree at most. If the node X can arrive the other node Y, it will contribute a[X]^a[Y]. You are asked to calculate the contribution of the whole graph.
Analysis
The first point we know is that this graph can only be composed by a single ring, or a tree which the edge direction is opposite. And if there is a ring in the tree, it must be the root.
For each ring, we can compute the contribution separately assuming there are no trees mentioned above. How to compute? Count the number of 0 and 1 of all nodes' 32 bits of the ring. Then it's easy to enumerate each node to calculate the xor contribution with other nodes.
We ignore the tree in the last paragraph, now we consider it. If no ring in a tree, that's easy. Just use DFS to traverse, and for each DFS chain, compute like the node is in a ring, the only difference is that the edge of tree is unidirectional, so you can only calculate the xor contribution with the ancestor nodes. And if the root of tree is a ring, the only extra thing we should do is to count all nodes'bit of the ring but not compute contribution with each others.
We use tarjan algorithm to find the SCC(in this problem, all is a ring or a single node).
Code
The dirty code in the competition, but I am lazy to prettify it.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50;
typedef long long ll;
const ll mod=1e9+7;
int n;
int a[N],d[N];
vector<int> g[N];
int p[N],low[N],scc[N];
int cnt;
int clk;
stack<int> sta;
void dfs(int u){
p[u]=low[u]=++clk;
sta.push(u);
int siz=g[u].size();
for(int i=0;i<siz;i++){
int v=g[u][i];
if(!p[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!scc[v]){
low[u]=min(low[u],p[v]);
}
}
if(low[u]==p[u]){
cnt++;
while(true){
int x=sta.top();
sta.pop();
scc[x]=cnt;
if(x==u){
break;
}
}
}
}
// chu shi hua
ll ans;
vector<int> h[N];
int in[N];
vector<int> sccs[N];
int one[35];
int zero[35];
void dfs2(int u){
int siz=sccs[u].size();
for(int i=0;i<siz;i++){
int data=a[sccs[u][i]];
for(int k=0;k<32;k++){
int b=(data>>k)&1;
if(b==1){
one[k]++;
}else{
zero[k]++;
}
}
}
if(in[u]!=0){
for(int i=0;i<siz;i++){
int data=a[sccs[u][i]];
for(int k=0;k<32;k++){
int b=(data>>k)&1;
if(b==1){
ans+=(1LL<<k)*zero[k]%mod;
ans%=mod;
}else{
ans+=(1LL<<k)*one[k]%mod;
ans%=mod;
}
}
}
}
int hsize=h[u].size();
for(int i=0;i<hsize;i++){
int v=h[u][i];
dfs2(v);
}
for(int i=0;i<siz;i++){
int data=a[sccs[u][i]];
for(int k=0;k<32;k++){
int b=(data>>k)&1;
if(b==1){
one[k]--;
}else{
zero[k]--;
}
}
}
}
template <class T>
inline bool scan_d(T &ret){
char c;
int sgn;
if(c=getchar(),c==EOF)return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&& c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
int main(){
int T;
// scanf("%d",&T);
scan_d(T);
while(T--){
// scanf("%d",&n);
scan_d(n);
for(int i=1;i<=n;i++){
g[i].clear();
p[i]=0;
low[i]=0;
scc[i]=0;
in[i]=0;
sccs[i].clear();
h[i].clear();
}
for(int i=1;i<=n;i++){
// scanf("%d",&a[i]);
scan_d(a[i]);
}
for(int i=1;i<=n;i++){
// scanf("%d",&d[i]);
scan_d(d[i]);
if(d[i]!=0){
g[i].push_back(d[i]);
}
}
clk=0;
cnt=0;
for(int i=1;i<=n;i++){
if(!p[i]){
dfs(i);
}
}
for(int i=1;i<=n;i++){
if(d[i]){
if(scc[i]!=scc[d[i]]){
h[scc[d[i]]].push_back(scc[i]);
in[scc[i]]++;
}
}
}
for(int i=1;i<=n;i++){
sccs[scc[i]].push_back(i);
}
ans=0;
for(int i=1;i<=cnt;i++){
int siz=sccs[i].size();
memset(one,0,sizeof(one));
memset(zero,0,sizeof(zero));
for(int j=0;j<siz;j++){
int data=a[sccs[i][j]];
for(int k=0;k<32;k++){
int b=(data>>k)&1;
if(b==1){
one[k]++;
}else{
zero[k]++;
}
}
}
for(int j=0;j<siz;j++){
int data=a[sccs[i][j]];
for(int k=0;k<32;k++){
int b=(data>>k)&1;
if(b==1){
ans+=(1LL<<k)*zero[k]%mod;
ans%=mod;
}else{
ans+=(1LL<<k)*one[k]%mod;
ans%=mod;
}
}
}
}
for(int i=1;i<=cnt;i++){
if(in[i]==0 && h[i].size()!=0){
memset(one,0,sizeof(one));
memset(zero,0,sizeof(zero));
dfs2(i);
}
}
printf("%lld\n",ans%mod);
}
return 0;
}