/***********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;
}
(LightOJ) 1304 – The Best Contest Site Ever
0
/***********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 5100
#define MAXX 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;
}
}kuhn;
char grid[MAXX][MAXX];
int N, M;
#define index sflajfsa
paii index[MAXX][MAXX];
void solve()
{
int r = 0, c = 0;
loop(i, N)
{
loop(j, M)
{
if(j == 0)
{
r++;
if(grid[i][j] == '.')
{
index[i][j].fr = r;
}
}
else
{
if(grid[i][j] == '.')
{
index[i][j].fr = r;
}
else
{
index[i][j].fr = -1;
if(grid[i][j] == 'W' && grid[i][j-1] != 'W' )
{
r++;
}
}
}
}
}
loop(j, M)
{
loop(i, N)
{
if(i == 0)
{
c++;
if(grid[i][j] == '.')
{
index[i][j].sc = c;
}
}
else
{
if(grid[i][j] == '.')
{
index[i][j].sc = c;
}
else
{
index[i][j].sc = -1;
if(grid[i-1][j] != 'W' && grid[i][j] == 'W')
{
c++;
}
}
}
}
}
kuhn.clear(r+2);
loop(i, N)
{
loop(j, M)
{
if(grid[i][j] == '.')
{
kuhn.adj[ index[i][j].fr ].pb( index[i][j].sc );
}
}
}
int m = kuhn.match(r + 2);
pf("%d\n", m);
int u, v;
loop(i, N)
{
loop(j, M)
{
if(grid[i][j] == '.')
{
u = index[i][j].fr;
v = index[i][j].sc;
if(kuhn.left[u] == v)
{
pf("T");
}
else
{
pf(".");
}
}
else
{
pf("%c", grid[i][j]);
}
}
pf("\n");
}
}
int main()
{
#ifdef hasibpc
read("input.txt");
//write("output.txt");
#endif
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%d %d", &N, &M);
loop(i, N)
{
sf("%s", grid[i]);
}
pf("Case %d: ", ++kaseno);
solve();
}
}
(LightOJ) 1218 – Multiple Free Subset
0Step 1. Sort the array.
Step 2. Remove duplicates.
Step 3. Make a bipartite graph. There should be a connection from i to j iff i divides j.
Step 4. Start from the smallest number, and follow the next steps repeatedly.
– Remove all the multiples of this number from the graph. Remove from both sides of bipartite graph.
– Now check, if we can create exactly same size of maximum independent set as before.
– If possible, parmanently delete those multiples and push the current number into result array. If not possible, restore the previous graph.
/***********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
*/
int N;
vector<int>v;
#define NODE 107
int mark[NODE];
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(mark[t]) continue;
if(right[t] == -1)
{
right[t] = v; left[v] = t;
return true;
}
}
loop(i, SZ(adj[v]))
{
int t = adj[v][i];
if(mark[t]) continue;
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(mark[i]) continue;
if(left[i] == -1 && tryK(i))
{
done = false;
}
}
}while(!done);
FOR(i, 0, n)
{
if(mark[i]) continue;
res += (left[i] != -1);
}
return res;
}
}kuhn;
void solve()
{
sort(all(v));
UNIQUE(v);
N = SZ(v);
kuhn.clear(N + 2);
loop(i, N)
{
for(int j=i+1; j<N; j++)
{
if( (v[j] % v[i]) == 0 )
{
//vdump(MP(i,j));
kuhn.adj[i].pb(j);
}
}
}
mem(mark, 0);
int M = N - kuhn.match(N+2);
vector<int>result;
int m;
int prevMarked = 0;
loop(i, N)
{
if(mark[i]) continue;
m = 0;
for(int j=i+1; j<N; j++)
{
if( (mark[j] == 0) && (v[j] % v[i] == 0) )
{
mark[j] = 2;
m++;
}
}
int tmp = (N - m - prevMarked - kuhn.match(N+2));
if(tmp == M )
{
result.pb(i);
prevMarked += m;
m = 1;
}
else
{
m = 0;
}
loop(i, N)
{
if(mark[i] == 2)
{
mark[i] = m;
}
}
}
loop(i, M)
{
pf(" %d", v[result[i]]);
}
pf("\n");
}
int main ()
{
#ifdef hasibpc
read("input.txt");
//write("output.txt");
#endif // hasibpc
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%d", &N);
v.resize(N);
loop(i, N)
{
sf("%d", &v[i]);
}
pf("Case %d:", ++kaseno);
solve();
}
return 0;
}
(LightOj) 1199 – Partitioning Game
0
/***********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 MAXX 10007
int ara[107], N;
int g[10007];
void precalc()
{
g[0] = g[1] = 0;
int marked[MAXX];
int x;
mem(marked, 0);
for(int i=2; i<MAXX; i++)
{
for(int j=1, k = i-1; j<k; j++, k--)
{
x = g[j] ^ g[k];
marked[x] = i;
}
for(int j=0; j<MAXX; j++)
{
if(marked[j] != i)
{
g[i] = j;
break;
}
}
}
}
void solve()
{
int x = 0;
loop(i, N)
{
x ^= g[ ara[i] ];
}
if(x == 0)
{
pf("Bob\n");
}
else
{
pf("Alice\n");
}
}
int main ()
{
#ifdef hasibpc
//read("input.txt");
//write("output.txt");
#endif // hasibpc
precalc();
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%d", &N);
loop(i, N)
{
sf("%d", &ara[i]);
}
pf("Case %d: ", ++kaseno);
solve();
}
return 0;
}
(LightOJ) 1201 – A Perfect Murder
0
/*
Firstly bi-colored all nodes using a simple dfs. After that all red nodes is on left side
and all black nodes on the right side. Now made connection between nodes according to given edge.
Result is: N - bpm.
Why it works?
-------------
We need to find maximum set which are not connected at all.
As we calculated bpm, it's maximum flow that can run through this network.
Now, we know max-flow = min-cut.
Here in bipartite graph, min-cut will be applied only on the edges like source->node or node->sink (can be proven
by greedy choice).
Thus, min-cut means: minimum number of node to be deleted to make this graph disconnected, i.e, no flow will
pass through this network after removing those node.
so, (N - bpm) is maximum set size which are not connected by any edge. That's the answer.
*/
/***********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 1007
#define MAXX NODE
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;
for ( int i = 0; i < SZ(adj[v]); i++ ) {
int t = adj[v][i];
if ( right[t] == -1 ) {
right[t] = v; left[v] = t;
return true;
}
}
for ( int i = 0; i < SZ(adj[v]); i++ ) {
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;
}
}kuhn;
vector<int>graph[MAXX];
int N, M;
int color[MAXX];
void init()
{
for(int i=1; i<=N; i++)
{
graph[i].clear();
kuhn.adj[i].clear();
color[i] = -1;
}
}
void dfs(int u, int c)
{
color[u] = c;
int v;
loop(i, SZ(graph[u]))
{
v = graph[u][i];
if(color[v] == -1)
{
dfs(v, c ^ 1);
}
}
return;
}
int solve()
{
for(int i=1; i<=N; i++)
{
if(color[i] == -1)
{
dfs(i, 0);
}
}
for(int i=1; i<=N; i++)
{
if(color[i] == 0)
{
loop(j, SZ(graph[i]))
{
kuhn.adj[i].pb(graph[i][j]);
}
}
}
return N - kuhn.match(N);
}
int main ()
{
#ifdef hasibpc
//read("input.txt");
//write("output.txt");
#endif // hasibpc
int kases, kaseno = 0;
int a, b;
sf("%d", &kases);
while(kases--)
{
sf("%d %d", &N, &M);
init();
while(M--)
{
sf("%d %d", &a, &b);
graph[a].pb(b);
graph[b].pb(a);
}
pf("Case %d: %d\n", ++kaseno, solve());
}
return 0;
}
(LightOj) 1126 – Building Twin Towers
0The main idea is: dp[i][j] represent what is the maximum sum of two towers when the difference is j.
/***********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 MAXX 57
#define MAXSUM 500007
int ara[MAXX];
int N;
int dp[2][MAXSUM];
int solve()
{
mem(dp, -1);
dp[0][0] = 0;
int now, pre;
now = 1, pre = 0;
loop(i, N)
{
loop(j, MAXSUM)
{
if(dp[pre][j] != -1)
{
dp[now][j] = max(dp[now][j], dp[pre][j]);
int diff = abs(j - ara[i]);
dp[now][diff] = max(dp[now][diff], max(dp[pre][diff], dp[pre][ j ] + ara[i] ));
//pf("dp[%d] = %d\n", diff, dp[now][diff]);
diff = j + ara[i];
dp[now][diff] = max(dp[now][diff], max(dp[pre][diff], dp[pre][ j ] + ara[i] ));
//pf("dp[%d] = %d\n", diff, dp[now][diff]);
}
}
swap(now, pre);
}
return max(dp[now][0], dp[pre][0]);
}
int main ()
{
#ifdef hasibpc
read("input.txt");
//write("output.txt");
#endif // hasibpc
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%d", &N);
loop(i, N)
{
sf("%d", &ara[i]);
}
sort(ara, ara+N); ///optimization 😀
int ret = solve();
if(ret != 0)
{
pf("Case %d: %d\n",++kaseno, ret/2);
}
else
{
pf("Case %d: impossible\n", ++kaseno);
}
}
return 0;
}
(LightOj) 1014 – Ifter Party
0
Note the looping style for finding divisors. It’s the perfect way! Don’t try otherwise, or you will get Wrong divisors for 2.
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#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
ll P, L;
//vector<ll>choto, boro;
vector<ll> result;
int main()
{
int kases, kaseno = 0;
sf("%d", &kases);
while(kases--)
{
sf("%lld %lld", &P, &L);
ll N = P - L;
ll root = sqrt(N);
result.clear();
//ll till = max(L, root);
for(ll q = 1; q<=root; q++)
{
if( (N%q) == 0)
{
if(q > L)
{
result.pb(q);
}
if( (q*q != N) && (N/q) > L)
{
result.pb(N/q);
}
}
}
//dump(result);
sort(all(result));
pf("Case %d:", ++kaseno);
if(SZ(result))
{
loop(i, SZ(result))
{
pf(" %lld", result[i]);
}
pf("\n");
}
else
{
pf(" impossible\n");
}
}
return 0;
}
(CodeForces) B. Symmetric and Transitive
0comp[k] = How many ways a set of k elements can be written as a summation of few component.
Suppose S = {1, 2, 3}.
Here k = 3;
S = {1, 2, 3}
= {1, 2} + {3}
= {1, 3} + {2}
= {2, 3} + {1}
= {1} + {2} + {3}
So, comp[3] = 5.
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#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 4007
#define MOD 1000000007
#define POWMAX 7998007
int n;
ll nCr[MAXX][MAXX];
ll ara[MAXX][MAXX];
ll comp[MAXX];
void calc()
{
ara[1][1] = 1;
comp[0] = 1;
comp[1] = 1;
for(int i=2; i<MAXX; i++)
{
comp[i] = 1;
ara[i][1] = 1;
for(int j=2; j<=i; j++)
{
ara[i][j] = (ara[i-1][j-1] + (j * ara[i-1][j])%MOD )%MOD;
comp[i] = (comp[i] + ara[i][j])%MOD;
}
}
}
int main()
{
calc();
nCr[1][0] = nCr[1][1] = 1;
for(int i=2; i<MAXX; i++)
{
nCr[i][0] = 1;
for(int j=1; j<=i; j++)
{
nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1])%MOD;
}
}
cin>>n;
ll ret = 0;
for(int i=0; i<n; i++)
{
ll tmp = nCr[n][i] * comp[i];
ret = (ret + tmp%MOD)%MOD;
}
cout<<ret<<endl;
}
(LightOj) 1291 – Real Life Traffic
0
/****************************************************************
▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄
███ ███ ███ ███ ███ ███ ███ ███ ███
███ ███ ███ ███ ███ █▀ ███ ███ ███
▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
███ ███ ███ ███ ███ ███ ███ ██▄
███ ███ ███ ███ ▄█ ███ ███ ███ ███
███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀
****************************************************************/
#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
vector<int>graph[MAXX];
int n, m;
map<int, map<int, int> > isBridge;
bool visited[MAXX];
int low[MAXX], disc[MAXX];
int parent[MAXX];
int t;
vector<paii>bridges;
int cnt[MAXX];
void dfs_bridge(int u)
{
visited[u] = true;
low[u] = disc[u] = ++t;
loop(i, SZ(graph[u]))
{
int v = graph[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(MP(u, v));
isBridge[u][v] = isBridge[v][u] = 1;
}
}
else if( v != parent[u])
{
low[u] = min(low[u], disc[v]);
}
}
}
int find(int u)
{
if(u == parent[u]) return u;
else return parent[u] = find(parent[u]);
}
int main()
{
int kases, kaseno = 0;
take(kases);
while(kases--)
{
loop(i, MAXX) graph[i].clear();
isBridge.clear();
take(n, m);
int u, v;
loop(i, m)
{
take(u, v);
graph[u].pb(v);
graph[v].pb(u);
}
mem(visited, 0);
mem(parent, -1);
t = 0;
bridges.clear();
loop(i, n)
{
if(!visited[i])
{
dfs_bridge(i);
}
}
loop(i, n)
{
parent[i] = i;
}
loop(i, n)
{
loop(j, SZ(graph[i]))
{
int v = graph[i][j];
if(isBridge[i][v] != 1)
{
//cerr<<"i is "<<i<<" and v = "<<v<<" "<<isBridge[u][v]<<endl;
int u = find(i);
v = find(v);
if( u != v)
{
parent[u] = v;
//cerr<<"connecting "<<u<<" and "<<v<<endl;
}
}
else
{
//dump(u); dump(v);
//cerr<<"here"<<endl;
}
}
}
mem(cnt, 0);
loop(i, SZ(bridges))
{
int u = bridges[i].fr, v = bridges[i].sc;
u = find(u);
v = find(v);
//dump(u); dump(v);
cnt[u]++;
cnt[v]++;
}
int ret = 0;
loop(i, n)
{
if(cnt[i] == 1)
{
ret++;
}
}
//ret = count of leaf
ret = (ret + 1)/2;
pf("Case %d: %d\n", ++kaseno, ret);
}
}
(LightOj) 1063 – Ant Hills
0
// 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);
}
}
UnLucky Codes 