Submission #1238104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238104		i_love_mriti	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	148 ms	38080 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second

const int mxN = 2005;


vector<int> adj[mxN];
vector<vector<int>> ways(mxN,vector<int>(mxN,0));
bool vis[mxN];
/*vector<vector<int>> nways(mxN,vector<int>(mxN,0));*/

struct DSU{
	vector<int> sz,par;
	void init(int n){
		sz.resize(n,1);
		par.resize(n);
		for(int i=1;i<n;++i) par[i]=i;
	}
	int findPar(int u){
		if(par[u]==u) return u;
		return par[u]=findPar(par[u]);
	}
	void unite(int u,int v){
		int upar=findPar(u);
		int vpar=findPar(v);
		if(upar==vpar) return;
		if(sz[upar]>sz[vpar]){
			par[vpar]=upar;
			sz[upar]+=sz[vpar];
		}else{
			par[upar]=vpar;
			sz[vpar]+=sz[upar];
		}
	}
	bool same(int u,int v){
		return findPar(u)==findPar(v);
	}
} ds;

void dfs(int u,int lead){
	++ways[lead][u];
	vis[u]=1;
	for(auto it:adj[u]){
		if(!vis[it]) dfs(it,lead);
	}
	vis[u]=0;
}

/*void dfs2(int u,int lead){
	++nways[lead][u];
	vis[u]=1;
	for(auto it:adj[u]){
		if(!vis[it]) dfs(it,lead);
	}
	vis[u]=0;
}*/

/*
void build(vector<vector<int>> cadj){
	int n=cadj.size();


	for(int i=0;i<n;++i){
    	dfs2(i,i);
    	for(int j=0;j<n;++j){
    		vis[j]=0;
    	}
    }

   for(int i=0;i<n;++i){
    	for(int j=0;j<n;++j){
    		cout<<ways[i][j]<<" ";
    	}cout<<endl;
    }

}
*/



int construct(vector<vector<int>> p){
	int n=p.size();
	ds.init(n+6);
	vector<vector<int>> current_adj(n,vector<int>(n,0));


	for(int i=0;i<n;++i){
		vector<int> one_way={i};
		for(int j=0;j<n;++j){
			if(!ds.same(i,j)&&p[i][j]==1){
				ds.unite(i,j);
				current_adj[one_way.back()][j]=1;
				current_adj[j][one_way.back()]=1;
				one_way.pb(j);

				
			}
		}
	}


	for(int i=0;i<n;++i){
		vector<int> two_way={i};
		for(int j=0;j<n;++j){
			ways[i][j]=0;
			if(!ds.same(i,j)&&p[i][j]==2){
				ds.unite(i,j);
				current_adj[two_way.back()][j]=1;
				current_adj[j][two_way.back()]=1;

			
				two_way.pb(j);
			}
		}
		if(two_way.size()>1){
			current_adj[two_way.back()][i]=1;
			current_adj[i][two_way.back()]=1;
		}
	}

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(current_adj[i][j]){
				adj[i].pb(j);
				adj[j].pb(i);
			}
		}
	}

	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j) vis[j]=0;
		dfs(i,i);
	}

	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(ways[i][j]!=p[i][j]) return 0;
		}
	}

	build(current_adj);



	return 1;
}




/*
int main() {
    
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n,m,u,v;cin>>n>>m;
    for(int i=0;i<m;++i){
    	cin>>u>>v;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }

    ways.resize(n,vector<int>(n,0));

    for(int i=0;i<n;++i){
    	dfs(i,i);
    }

    for(int i=0;i<n;++i){
    	for(int j=0;j<n;++j){
    		cout<<ways[i][j]<<" ";
    	}cout<<endl;
    }



    construct(ways);

    return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4