fork download 
// Mera solution mat hi dekh yaar!

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define inp_s     ios_base::sync_with_stdio(false)
#define DRT()     int test_case;cin>>test_case;while(test_case--)

#define VI        vector<int>
#define VS        vector<string>
#define VLL       vector<LL>
#define PII       pair<int,LL>
#define all(c)    c.begin(),c.end()
#define sz(c)     (int)c.size()
#define clr(c)    c.clear()
#define pb        push_back
#define mp        make_pair

#define GI(x)     scanf("%d",&x)

#define FOR(i,a,b)      for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b)     for(int i=(int)(b)-1;i>=(int)(a);i--)

#define MOD       1000000007
#define EPS       1E-10

#define PI  acos(-1)

#define CASE(x)   cout << "Case #" << x << ": ";

LL f[1010][1010];
int n,m;
LL mod;

LL preprocess(int i , int j)
{
	if(i == j) return 0;
	else if(i == 1 || j == 1) return (1%mod);
	else if(f[i][j] != -1) return f[i][j];
	LL ret = (preprocess(i-1,j) + preprocess(i,j-1)) % mod;
	ret = (ret + preprocess(i-1,j-1)) % mod;
	return (f[i][j] = ret);
}

int isBridge[1010][1010];
vector<VI> graph;

int dfsTime = 1;
vector<int> low , disc;
int visited[1010];

void bridgeDFS(int u , int par)
{
	if(visited[u]) return ;
	low[u] = disc[u] = dfsTime++;
	visited[u] = 1;
	FOR(i,0,sz(graph[u]))
	{
		int v = graph[u][i];
		if(v == par) continue;

		if(!visited[v])
		{
			bridgeDFS(v, u);
			low[u] = min(low[u] , low[v]);
			if(low[v] > disc[u])
				isBridge[u][v] = isBridge[v][u] = 1;
		}
		else
			low[u] = min(low[u] , disc[v]);
	}
}

int conversion[1010] = {0};

void findBridges()
{
	FOR(i,0,1010) visited[i] = 0;
	bridgeDFS(1 , -1);
	FOR(i,0,1010) conversion[i] = i;
}

vector< vector<PII> > bridgeGraph;

void bridgeTree()
{
	FOR(i,0,1010) visited[i] = 0;
	FOR(ii,1,n+1)
	{
		if(visited[ii]) continue;
		queue<int> bfs;
		bfs.push(ii);
		visited[ii] = 1;
		while(!bfs.empty())
		{
			int ele = bfs.front();
			bfs.pop();
			FOR(i,0,sz(graph[ele]))
			{
				int v = graph[ele][i];
				if(isBridge[ele][v]) continue;
				if(visited[v] == 0)
				{
					conversion[v] = ii;
					visited[v] = 1;
					bfs.push(v);
				}
			}
		}
	}
	clr(bridgeGraph);
	bridgeGraph.resize(n + 1);
	FOR(i,1,n+1)
	{
		FOR(j,1,n+1)
		{
			if(isBridge[i][j])
			{
				int u = conversion[i];
				int v = conversion[j];
				bridgeGraph[u].pb(mp(v , f[i][j]));
				bridgeGraph[v].pb(mp(u , f[i][j]));
			}
		}
	}
}

LL cost[1010][1010] = {{0}};
LL shortestBridge[1010][1010] = {{0}};

void getans()
{
	FOR(i,0,1010) FOR(j,0,1010) cost[i][j] = 0 ,shortestBridge[i][j] = INT_MAX;
	FOR(i,1,n+1) FOR(j,1,n+1)
	{
		int u = conversion[i];
		int v = conversion[j];
		if(u == v) cost[u][v] = cost[v][u] = 0;
		else cost[u][v] = cost[v][u] = max(cost[u][v] , f[i][j]);
	}
	FOR(i,1,n+1)
	{
		FOR(ii,0,1010) visited[ii] = 0;
		int u = conversion[i];
		if(visited[u]) continue;
		queue<PII> bfs;
		bfs.push(mp(u,INT_MAX));

		visited[u] = 1;
		while(!bfs.empty())
		{
			PII ele = bfs.front();
			bfs.pop();
			u = ele.first;
			LL c = ele.second;
			FOR(ii,0,sz(bridgeGraph[u]))
			{
				PII q = bridgeGraph[u][ii];
				if(visited[q.first]) continue;
				visited[q.first] = 1;
				shortestBridge[conversion[i]][q.first] = shortestBridge[q.first][conversion[i]] = min(q.second , c);
				bfs.push(mp(q.first , min(q.second , c) ));
			}
		}
	}
	LL ans = 0;
	FOR(i,1,n+1)
	{
		FOR(j,1,n+1)
		{
			int u = conversion[i];
			int v = conversion[j];
			if(u == v) continue;
			ans = max(ans , cost[u][v] - shortestBridge[u][v]);
		}
	}
	cout << ans << endl;
}

int main()
{
	inp_s;
	DRT()
	{
		clr(low);
		clr(disc);
		clr(graph);
		dfsTime = 1;

		cin >> n >> m >> mod;
		graph.resize(n + 1);
		FOR(i,0,1010) FOR(j,0,1010) isBridge[i][j] = 0, f[i][j] = -1;
		FOR(i,1,1010) FOR(j,1,1010) f[i][j] = preprocess(i,j);
		//step 1 : preprocess , done!
		FOR(i,0,m)
		{
			int a,b;
			cin >> a >> b;
			graph[a].pb(b);
			graph[b].pb(a);
		}
		low.resize(n + 1);
		disc.resize(n + 1);
		findBridges();
		//step 2 : finding bridges, done.
		bridgeTree();
		//step 3 : create the bridge tree, done.
		getans();
		//step 4 : this is what they need.. wonder why i couldnt make this step 1. 
	}
	return 0;
}
Runtime error #stdin #stdout 0s 31328KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Mfu9PK
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!