Monthly Archives: July 2015

(LightOj) 1063 – Ant Hills

0
Posted on by 

// link: http://lightoj.com/volume_showproblem.php?problem=1063
// tuto: http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


#define MAXX 10007


int N, M;

vector<int>adj[MAXX];

bool visited[MAXX];
int parent[MAXX];

int low[MAXX];
int disc[MAXX];

int tyme;

bool isArticulationPoint[MAXX];


void init()
{
	loop(i, MAXX)
	{
		adj[i].clear();
		visited[i] = false;
		parent[i] = -1;
		isArticulationPoint[i] = false;
	}

	tyme = 0;
}


void dfs_articulation_point(int u)
{
	visited[u] = true;

	disc[u] = low[u] = ++tyme;

	int cntChild = 0;

	loop(i, SZ(adj[u]))
	{
		int v = adj[u][i];

		if( ! visited[v] )
		{
			cntChild++;
			parent[v] = u;

			dfs_articulation_point(v);

			low[u] = min(low[u], low[v]);

			

			if(parent[u] != -1)	
			{
				if(low[v] >= disc[u])
				{
					isArticulationPoint[u] = true;
				}
			}


		}
		else if(v != parent[u])
		{
			low[u] = min(low[u], disc[v]);
		}
	}
	
	if(parent[u] == -1)
	{
		if(cntChild > 1)
		{
			isArticulationPoint[u] = true;
		}
	}


}


int main()
{
	int kases, kaseno = 0;

	take(kases);

	while(kases--)
	{
		take(N, M);
		
		init();

		int u, v;

		loop(i, M)
		{
			take(u, v);

			adj[u].pb(v);
			adj[v].pb(u);
		}
		

		for(int i=1; i<=N; i++)
		{
			if( ! visited[i] )
			{
				dfs_articulation_point(i);
			}
		}

		int cntArticulationPoint = 0;

		for(int i=1; i<=N; i++)
		{
			if(isArticulationPoint[i]) cntArticulationPoint++;
		}

		pf("Case %d: %d\n",++kaseno, cntArticulationPoint);
	}





}

(LighOj) 1026 – Critical Links

0
Posted on by 
//link: http://lightoj.com/volume_showproblem.php?problem=1026
//tuto: http://www.geeksforgeeks.org/bridge-in-a-graph/
/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here

#define MAXX 10007


int n;
vector<int>adj[MAXX];

int tyme;

bool visited[MAXX];
int parent[MAXX];

int low[MAXX];
int disc[MAXX];

vector<paii>bridges;



void dfs_bridge(int u)
{
	visited[u] = true;

	disc[u] = low[u] = ++tyme;

	int child = 0;

	loop(i, SZ(adj[u]))
	{
		int v = adj[u][i];

		if( ! visited[v])
		{
			parent[v] = u;

			dfs_bridge(v);

			low[u] = min(low[u], low[v]);

			if( low[v] > disc[u] )
			{
				bridges.pb(min(MP(u, v), MP(v, u)));
			}
			
		}
		else if( v != parent[u] )
		{
			low[u] = min(low[u], disc[v]);
		}
	}

	


}



int main()
{
	int kases, kaseno = 0;

	sf("%d", &kases);

	while(kases--)
	{
		sf("%d", &n);

		int u, k, v;
		char ch;

		loop(i, n)
		{
			adj[i].clear();
			parent[i] = -1;
			visited[i] = false;
		}

		bridges.clear();

		loop(i, n)
		{

			sf("%d %c%d%c", &u, &ch, &k, &ch);

			loop(j, k)
			{
				sf("%d", &v);

				adj[u].pb(v);
			}
		}

		loop(i, n)
		{
			if( ! visited[i] )
			{
				dfs_bridge(i);
			}
		}
		
		pf("Case %d:\n", ++kaseno);
		pf("%d critical links\n", SZ(bridges));
		
		sort(all(bridges));

		loop(i, SZ(bridges))
		{
			pf("%d - %d\n", bridges[i].fr, bridges[i].sc);
		}



	}





}

(CodeChef) MasterChef

0
Posted on by

A nice idea with memory optimization for Knapsack dp


// Link: http://www.codechef.com/JULY15/problems/MCHEF/


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here


#define MAXX 100007

#define INF 16843009


int N, M;
int K;
ll ara[MAXX];

int L, R, C;

int sum[4*MAXX];

ll dp[507];


void update(int idx, int st, int ed, int i, int j, int val)
{
	if(st == i && ed == j)
	{
		sum[idx] = min(sum[idx], val);
		return;
	}


	int l = idx*2;
	int r = l + 1;
	int mid = (st + ed)/2;


	sum[l] = min(sum[l], sum[idx]);
	sum[r] = min(sum[r], sum[idx]);

	sum[idx] = INF;

	if(j <= mid)
	{
		update(l, st, mid, i, j, val);
	}
	else if(mid < i)
	{
		update(r, mid+1, ed, i, j, val);
	}
	else
	{
		update(l, st, mid, i, mid, val);
		update(r, mid+1, ed, mid+1, j, val);
	}
}



int get(int idx, int st, int ed, int pos)
{
	if(st == ed)
	{
		return sum[idx];
	}


	int l = idx*2;
	int r = l + 1;
	int mid = (st + ed)/2;

	if(sum[idx] != INF)
	{
		sum[l] = min(sum[l], sum[idx]);
		sum[r] = min(sum[r], sum[idx]);
		sum[idx] = INF;
	}


	if(pos <= mid)
	{
		return get(l, st, mid, pos);
	}
	else
	{
		return get(r, mid+1, ed, pos);
	}
}



void init()
{
	mem(sum, 1);

	mem(dp, 0);
}



int main()
{
	//init(); cout<<sum[0];
	int kases;


	take(kases);

	while(kases--)
	{
		init();
		take(N, K, M);

		ll s = 0;

		loop(i, N)
		{
			take(ara[i]);

			s += ara[i];
		}

		loop(i, M)
		{
			take(L, R, C);

			update(1, 0, N-1, L-1, R-1, C);
		}

		//cerr<<"DONE"<<endl;

		loop(i, N)
		{
			if(ara[i] < 0)
			{
				ll tmp = -ara[i];

				//dump(tmp);

				C = get(1, 0, N-1, i);

				//dump(C);

				for(int pos=K; pos>=0; pos--)
				{
					if(pos + C <= K)
					{
						dp[pos + C] = max(dp[pos + C], dp[pos] + tmp );
					}
				}
			}
		}


		cout<< s + dp[K]<<endl;
	}

}