/***********Template Starts Here***********/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <climits>
#include <iomanip>
#include <cassert>
//#include <unordered_map>
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((int)(x).size())
#define NORM(x) if(x>=mod)x-=mod;
using namespace std;
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;
#ifdef forthright48
#include <ctime>
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
#define debug(args...) // Just strip off all debug tokens
#define timeStamp
#endif
struct debugger{
template<typename T> debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
inline vlong gcd ( vlong a, vlong b ) {
a = ABS ( a ); b = ABS ( b );
while ( b ) { a = a % b; swap ( a, b ); } return a;
}
vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
x2 = 1; y2 = 0;
x1 = 0; y1 = 1;
for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
q = r2 / r1;
r = r2 % r1;
x = x2 - (q * x1);
y = y2 - (q * y1);
}
*X = x2; *Y = y2;
return r2;
}
inline vlong modInv ( vlong a, vlong m ) {
vlong x, y;
ext_gcd( a, m, &x, &y );
if ( x < 0 ) x += m; //modInv is never negative
return x;
}
inline vlong power ( vlong a, vlong p ) {
vlong res = 1, x = a;
while ( p ) {
if ( p & 1 ) res = ( res * x );
x = ( x * x ); p >>= 1;
}
return res;
}
inline vlong bigmod ( vlong a, vlong p, vlong m ) {
vlong res = 1 % m, x = a % m;
while ( p ) {
if ( p & 1 ) res = ( res * x ) % m;
x = ( x * x ) % m; p >>= 1;
}
return res;
}
/***********Template Ends Here***********/
/*********** Hasib Templates Starts Here**********/
#include<bits/stdc++.h>
using namespace std;
#define loop(i, n) for(int i=0; i<(n); i++)
#define sf scanf
#define pf printf
#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, val) memset(ara, val, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define vdump(x) cerr<<#x<<" = "<<x<<endl;
#define dump(args...) cerr,args; cerr<<endl
template<typename T>
ostream& operator<<(ostream& out, vector<T> v)
{
out<<"[ ";
loop(i, SZ(v))
{
if(i) out<<", ";
out<<v[i];
}
out<<" ]";
return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &out, pair<T1, T2> p)
{
out<<"( "<<p.fr<<", "<<p.sc<<")";
return out;
}
template<typename T>
ostream& operator,(ostream &out, T x)
{
out<<x<<" ";
return out;
}
/**********Hasib Templates Ends Here**************/
/**
* WARTNING for me:
* Never use FOR
* Never use pii, pll, vi, vi
* Never use ff, ss, phl, sp, nl
*/
#define NODE 107
struct KUHN{
int left[NODE], right[NODE], vis[NODE], cc;
vector<int> adj[NODE];
KUHN() : cc(1) {
}
void clear(int n)
{
FOR(i, 0, n) adj[i].clear();
}
bool tryK(int v)
{
if(vis[v] == cc) return false;
vis[v] = cc;
loop(i, SZ(adj[v]))
{
int t = adj[v][i];
if(right[t] == -1)
{
right[t] = v; left[v] = t;
return true;
}
}
loop(i, SZ(adj[v]))
{
int t = adj[v][i];
if( tryK(right[t]))
{
right[t] = v; left[v] = t;
return true;
}
}
return false;
}
int match(int n)
{
int res = 0;
bool done;
CLR(left, -1); CLR(right, -1);
do{
done = true; cc++;
FOR(i, 0, n)
{
if(left[i] == -1 && tryK(i))
{
done = false;
}
}
}while(!done);
FOR(i, 0, n) res += (left[i] != -1);
return res;
}
};
vector<int>original[NODE], modified[NODE];
int orgN, modN;
bool orgVisited[NODE], modVisited[NODE];
bool isMatch[NODE][NODE];
bool match(int u, int v)
{
orgVisited[u] = modVisited[v] = true;
int uu, vv;
KUHN kuhn;
/// !wow! Got WA because I took kuhn as local variable, and didn't clear visited!
mem(kuhn.vis, 0);
kuhn.clear(NODE-1);
loop(i, SZ(original[u]))
{
uu = original[u][i];
if(orgVisited[uu]) continue;
loop(j, SZ(modified[v]))
{
vv = modified[v][j];
if(modVisited[vv]) continue;
if(match(uu, vv))
{
kuhn.adj[i].pb(j);
}
}
}
orgVisited[u] = modVisited[v] = false;
int m = kuhn.match( SZ(original[u]) + 2 );
int child = SZ(original[u]) - 1;
if(u == 1) child++;
bool ret = (m == child);
return ret;
}
void solve()
{
//mem(orgVisited, 0); ///
//mem(modVisited, 0); ///
bool ret = match(1, 1);
if(ret)
{
pf("Yes\n");
}
else
{
pf("No\n");
}
}
int main ()
{
#ifdef hasibpc
read("input.txt");
//write("output.txt");
#endif // hasibpc
int kases, kaseno = 0;
int u, v;
sf("%d", &kases);
while(kases--)
{
sf("%d", &modN);
FOR(i, 0, modN) modified[i].clear();
for(int i=1; i<modN; i++)
{
sf("%d %d", &u, &v);
//debug(u, v);
modified[u].pb(v);
modified[v].pb(u);
}
//vdump(endl);
sf("%d", &orgN);
FOR(i, 0, orgN) original[i].clear();
for(int i=1; i<orgN; i++)
{
sf("%d %d", &u, &v);
//debug(u, v);
original[u].pb(v);
original[v].pb(u);
}
pf("Case %d: ", ++kaseno);
solve();
}
return 0;
}
Category Archives: কিম্ভূতকিমাকার ঝামেলা
(UVa) 481 – What Goes Up
0
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=422
*/
//sometimes input can be exact your macro. It may cause RTE along with WA. So use Trick.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 100000
int INF = 0;
int cnt;
vector<int>input;
int LisLen = 0;
vector<int>result;
void Nlogk_LIS()
{
int temp = cnt + 2;
int pos[temp], L[temp];
FOR(i, 1, temp)
{
pos[i] = INF;
}
pos[0] = -INF;
loop(i, cnt)
{
int low = 0, high = LisLen, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(pos[mid] < input[i])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
pos[low] = input[i];
L[i] = low;
LisLen = max(LisLen, low);
}
int last_taken = INF;
result.pb(cnt);
for(int i=LisLen; i>0; i--)
{
for(int j=result[LisLen - i] - 1; j>-1; j--)
{
if(L[j] == i && input[j] < last_taken)
{
result.pb(j);
last_taken = input[j];
break;
}
}
}
}
int main()
{
int n;
while(getint(n)!= EOF)
{
input.pb(n);
INF = max(INF, abs(n) );
}
INF += 2;
cnt = SZ(input);
Nlogk_LIS();
pf("%d\n-\n", LisLen);
for(int i=LisLen; i>0; i--)
{
pf("%d\n", input[ result[i] ]);
}
}
(UVa) 11553 – Grid Game
0The following two expression is NOT same.
1<<N - 1
(1<<N) - 1
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2548
time: 0.068 sec
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 10
int grid[MAXX][MAXX];
int dp[1<<MAXX][1<<MAXX];
int N;
int rec(int alice, int bob)
{
int &ret = dp[alice][bob];
if(ret != -1) return ret;
ret = -INF;
int temp;
loop(i, N)
{
if( (alice & (1<<i)) == 0 )
{
temp = INF;
loop(j, N)
{
if( (bob & (1<<j)) == 0 )
{
temp = min(temp, grid[i][j] + rec((alice | (1<<i)), (bob | (1<<j))) );
}
}
ret = max(ret, temp);
}
}
return ret;
}
int main()
{
//read();
int kases;
getint(kases);
while(kases--)
{
getint(N);
loop(i, N)
{
loop(j, N)
{
getint(grid[i][j]);
}
}
mem(dp, -1);
dp[(1<<N)-1][(1<<N)-1] = 0;
pf("%d\n", rec(0, 0));
}
return 0;
}
(LightOj) 1337 – The Crystal Maze
0In this code, read() = freopen() isn’t working properly… I don’t know why?? 😦
/*
user: php
time: 0.128 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1337
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof(a))
#define SZ size()
#define pi acos(-1.0)
#define INF 1<<29
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define mod(a) (a>0?(a):(-a))
#define get(n) scanf("%d", &n)
#define MAXX 505
#define debug cout<<"ok"
int count_row, count_column;
char graph[MAXX][MAXX];
int* dp[MAXX][MAXX];
int value[MAXX][MAXX];
bool visited[MAXX][MAXX];
int p, q;
void dfs(int x, int y)
{
if(x<0 || x == count_row || y<0 || y == count_column || visited[x][y] || graph[x][y] == '#') return;
dp[x][y] = &value[p][q];
visited[x][y] = true;
if(graph[x][y] == 'C')
{
value[p][q]++;
}
dfs(x+1, y);
dfs(x-1, y);
dfs(x, y-1);
dfs(x, y+1);
return;
}
int main()
{
int kases, kaseno = 0;
int query;
get(kases);
while(kases--)
{
mem(visited, false);
get(count_row);
get(count_column);
get(query);
loop(i, count_row)
{
scanf("%s", graph[i]);
}
printf("Case %d:\n", ++kaseno);
loop(i, query)
{
get(p);
get(q);
p--;
q--;
if(graph[p][q] == '#')
{
printf("0\n");
continue;
}
if( ! visited[p][q] )
{
value[p][q] = 0;
dfs(p, q);
}
printf("%d\n", *(dp[p][q]));
}
}
return 0;
}
(LightOj) 1042 – Secret Origins
0In this problem i have discovered with astonishment that the following code will generate wrong thing!!
long long p = (1<<31); long long k = (1<<30); k = (k<<1); // wrong too!!!
But, this’ll generate correct output!!
long long p = (1<<31); p *= 2;
/*
user: php
time: 0.000 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1042
*/
#include<iostream>
#include<cstdio>
using namespace std;
int count(long long num)
{
int cnt = 0;
for(long long t=1; t<= num; t *= 2)
{
if((num & (t)) != 0)
{
cnt++;
}
}
return cnt;
}
long long int next(long long int num)
{
long long res;
for(long long t = 1; t<= num; t *= 2)
{
if( (num & (t)) != 0)
{
res = num + t;
break;
}
}
int diff = count(num) - count(res) ;
for(int i=0; i<diff; i++)
{
res += (1<<i);
}
return res;
}
int main()
{
int kases, kaseno = 0;
long long int num;
scanf("%d", &kases);
while(kases--)
{
scanf("%lld", &num);
num = next(num);
printf("Case %d: %lld\n", ++kaseno, num);
}
return 0;
}
(UVa) 350 – Pseudo-Random Numbers
0
/*
user: php
time: 0.060 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=286
*/
#include<iostream>
#include<cstdio>
#include<map>
#define get(a) scanf("%d", &a)
using namespace std;
int main()
{
map<int, bool>mp;
int random, mul, add, mod, seed;
int kaseno = 0;
bool *t;
while(true)
{
get(mul);
get(add);
get(mod);
get(random);
if(mul == 0 && add == 0 && mod == 0 && random == 0 ) break;
seed = random;
mp.clear();
while(true)
{
t = &mp[random];
if(*t == true) break;
*t = true;
random = (random * mul + add) % mod;
}
printf("Case %d: %d\n", ++kaseno, mp.size() - (random!=seed));
}
}
(UVa) 11526 – H(n)
0
/*
user: php
time: 0.072 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2521
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long calc(int n)
{
int root = int(sqrt(n)) + 1; //if i remove the int( ) conversion, it's getting WA! Oh God, Why???
long long res = 0;
for(int i=1; i < root; i++)
{
res += n/i;
}
root--;
res = 2*res - root*root;
return res;
}
int main()
{
int kases, n;
scanf("%d", &kases);
while(kases--)
{
scanf("%d", &n);
printf("%lld\n", calc(n));
}
return 0;
}
UnLucky Codes 