#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#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 dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
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;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
#define MAXX 10003
struct graphNode{
int weight;
int v;
bool isProposedRoad;
};
struct node{
int cost;
int used;
int u;
bool operator<(const node &ob) const
{
return this->cost > ob.cost;
}
};
vector<graphNode>graph[MAXX];
int n, m, k, d;
int dist[11][MAXX];
int dijkstra()
{
//cerr<<endl;
node u, v;
u.u = u.cost = u.used = 0;
mem(dist, 1);
dist[0][0] = 0;
priority_queue<node>Q;
Q.push(u);
while(!Q.empty())
{
u = Q.top(); Q.pop();
//cerr<<"dist["<<u.u<<"]["<<u.used<<"] = "<<u.cost<<endl;
if(u.cost != dist[u.used][u.u]) continue;
if(u.u == n-1)
{
//dump(u.cost);
return u.cost;
}
loop(i, SZ(graph[u.u]))
{
//cerr<<u.u<<" -->"<<graph[u.u][i].v<<endl;
v.u = graph[u.u][i].v;
v.cost = graph[u.u][i].weight + u.cost;
v.used = u.used + (graph[u.u][i].isProposedRoad?1:0);
if(v.used <= d && v.cost < dist[v.used][v.u] )
{
dist[v.used][v.u] = v.cost;
Q.push(v);
//cerr<<"pushing "<<v.u<<" with cost "<<v.cost<<endl;
}
}
}
return -1;
}
int main()
{
int kases, kaseno = 0;
take(kases);
while(kases--)
{
graphNode aNode;
take(n, m, k, d);
loop(i, n) graph[i].clear();
int u, v, w;
aNode.isProposedRoad = false;
loop(i, m)
{
take(u, v, w);
aNode.weight = w;
aNode.v = v;
graph[u].pb(aNode);
}
aNode.isProposedRoad = true;
loop(i, k)
{
take(u, v, w);
aNode.weight = w;
aNode.v = v;
graph[u].pb(aNode);
}
int res = dijkstra();
if(res == -1) pf("Case %d: Impossible\n", ++kaseno);
else pf("Case %d: %d\n", ++kaseno, res);
}
}
Category Archives: struct
(UVa) 10226 – Hardwood Species
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#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 freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
#define ALPHA_LIST 128
struct node{
int cnt_trees;
node *child[ALPHA_LIST];
node()
{
cnt_trees = 0;
loop(i, ALPHA_LIST)
{
child[i] = NULL;
}
}
}*head;
int total;
/*
void clearTree(node *p)
{
loop(i, ALPHA_LIST)
{
if(p->child[i] != NULL)
{
clearTree(p->child[i]);
}
}
delete p;
}
void init()
{
head = new node();
}
int toint(char c)
{
if(c== ' ')
return 26;
if('a' <= c && c <= 'z')
return c - 'a';
else
return c - 'A';
}
*/
void insert(char *word)
{
//cout<<"inserting " << word<<endl;
node *current = head;
int ch;
while(*word != '\0')
{
ch = *word;
if(current->child[ch] == NULL)
current->child[ch] = new node();
current = current->child[ch];
word++;
}
current->cnt_trees++;
}
vector<char> name_list;
void printTree(node *current)
{
if(current->cnt_trees)
{
FOR(i, 0, SZ(name_list))
{
pf("%c", name_list[i]);
}
pf(" %.4lf\n", (100.0*current->cnt_trees)/(double)total);
//current->cnt_trees = 0;
}
loop(i, ALPHA_LIST)
{
if(current->child[i] != NULL)
{
name_list.pb(i);
printTree(current->child[i]);
name_list.pop_back();
}
}
delete current;
//current = NULL;
}
int main()
{
int kases;
char names[35];
bool blank = 0;
gi(kases);
cin.ignore();
cin.ignore();
while(kases--)
{
if(blank) pf("\n");
blank = 1;
head = new node();
//init();
//cout<<head<<endl;
total = 0;
while(gets(names))
{
if(strlen(names) == 0) break;
insert(names);
total++;
}
printTree(head);
//head = NULL;
//cout<<head<<endl<<endl<<endl;
//clearTree(head);
}
return 0;
}
(SPOJ) 1043. Can you answer these queries I
0
/*
user: hasib
link: http://www.spoj.com/problems/GSS1/
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl
using namespace std;
#define MAXX 50002
int cnt;
struct DATA{
int prefixsum, suffixsum, fullsum, maxsum;
};
DATA sum[4*MAXX];
DATA merge(DATA a, DATA b)
{
DATA result;
result.fullsum = a.fullsum + b.fullsum;
result.maxsum = max( a.maxsum, b.maxsum );
result.maxsum = max( result.maxsum, a.suffixsum + b.prefixsum );
result.prefixsum = max( a.prefixsum, a.fullsum + b.prefixsum );
result.suffixsum = max(b.suffixsum, b.fullsum + a.suffixsum);
return result;
}
void insert_update(int idx, int st, int ed, int pos, int value)
{
if(st == pos && pos == ed)
{
sum[idx].fullsum = sum[idx].maxsum = sum[idx].prefixsum = sum[idx].suffixsum = value;
return;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed)/2;
if(pos <= mid)
{
insert_update(l, st, mid, pos, value);
}
else
{
insert_update(r, mid+1, ed, pos, value);
}
sum[idx] = merge(sum[l], sum[r]);
}
DATA quer(int idx, int st, int ed, int i, int j)
{
if(st == i && ed == j) return sum[idx];
int l = idx<<1;
int r = l + 1;
int mid = (st + ed)/2;
if(j <= mid)
{
return quer(l, st, mid, i, j);
}
else if( i> mid)
{
return quer(r, mid+1, ed, i, j);
}
else
{
return merge( quer(l, st, mid, i, mid), quer(r, mid+1, ed, mid+1, j) );
}
}
int main()
{
//read();
DATA result;
getint(cnt);
int num;
for(int i=1; i<=cnt; i++)
{
getint(num);
insert_update(1, 1, cnt, i, num);
}
int m;
getint(m);
int p, q;
loop(i, m)
{
getint(p); getint(q);
result = quer(1, 1, cnt, p, q);
pf("%d\n", result.maxsum);
}
return 0;
}
(LightOj) 1018 – Brush (IV)
0
/*
user: php
link: http://lightoj.com/volume_showproblem.php?problem=1018
time: 0.772 sec
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
using namespace std;
#define ll long long
#define MAXX 17
#define check(mask, i) (mask & (1<<i))
#define set(mask, i) (mask | (1<<i))
struct DATA{
int x, y;
};
DATA places[MAXX];
int number_of_dust;
ll dp[1<<MAXX];
bool sameTriangle(int i, int j, int k)
{
return (places[j].y - places[i].y) * (places[k].x - places[i].x) == (places[j].x - places[i].x) * (places[k].y - places[i].y);
}
ll rec(int used)
{
/*
cout<<"calling ";
loop(i, number_of_dust)
{
if(check(used, i) == 0) cout<<0;
else cout<<1;
}
cout<<endl;
*/
ll &ret = dp[used];
if(ret != -1) return ret;
int cnt = 0;
loop(i, number_of_dust)
{
if(check(used, i) == 0) cnt++;
}
if(cnt == 1) return 1;
ret = INF;
loop(i, number_of_dust)
{
if(check(used, i) == 0)
{
int temp = (used | (1<<i));
FOR(j, i+1, number_of_dust)
{
int bt = (used | (1<<i));
if(check(temp, j) == 0)
{
temp = temp | (1<<j);
bt = bt | (1<<j);
loop(k, number_of_dust)
{
if(check(temp, k) == 0 && sameTriangle(i, j, k))
{
temp = temp | (1<<k);
bt = bt | (1<<k);
}
}
ret = min(ret, 1 + rec(bt));
}
}
break;
}
}
return ret;
}
int main()
{
int kases, kaseno = 0;
getint(kases);
while(kases--)
{
getint(number_of_dust);
loop(i, number_of_dust)
{
getint(places[i].x); getint(places[i].y);
}
mem(dp, -1);
dp[ (1<<number_of_dust) - 1 ] = 0;
pf("Case %d: %lld\n", ++kaseno, rec(0));
}
}
(UVa) 10051 – Tower of Cubes
0
/*
user: php
time: 0.108 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=992
*/
#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;
int s(int c)
{
if(c%2 == 0)
{
c++;
}
else
{
c--;
}
return c;
}
struct DATA{
int pos, col;
void set(int p, int c)
{
pos = p;
col = c;
}
};
DATA dir[502][7];
int numberofcubes;
int color[502][7];
int dp[502][7];
string name[] = {"front", "back", "left", "right", "top", "bottom"};
int longest(int pos, int c)
{
int &ret = dp[pos][c];
if(ret != -1) return ret;
int nc;
if(c % 2 == 0)
nc = c + 1;
else
nc = c - 1;
// c is the top color last;
// nc is to be new color
ret = 0;
FOR(i, pos+1, numberofcubes)
{
loop(j, 6)
{
if(color[i][j] == color[pos][nc])
{
if( ret < longest(i, j) )
{
ret = dp[i][j];
dir[pos][c].set(i, j);
}
}
}
}
return ++ret;
}
int main()
{
int maxcubes;
int kaseno = 0;
DATA it;
bool blank = false;
while(true)
{
getint(numberofcubes);
if(numberofcubes == 0) break;
loop(i, numberofcubes)
{
loop(j, 6)
{
getint(color[i][j]);
}
}
mem(dp, -1);
maxcubes = 0;
loop(i, numberofcubes)
{
loop(j, 6)
{
if(maxcubes < longest(i, j) )
{
it.set(i, j);
maxcubes = dp[i][j];
}
}
}
if(blank) pf("\n");
blank = true;
pf("Case #%d\n", ++kaseno);
pf("%d\n", maxcubes);
while(dp[it.pos][it.col] != 1)
{
pf("%d %s\n", it.pos+1, name[it.col].c_str());
it.set(dir[it.pos][it.col].pos, dir[it.pos][it.col].col);
}
pf("%d %s\n", it.pos+1, name[it.col].c_str());
}
return 0;
}
(UVa) 10258 – Contest Scoreboard
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1199
*/
#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(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
bool attendedteam[101];
struct DATA{
int id;
ll total;
ll tried[10];
bool solved[10];
int totalsolved;
};
DATA teamdata[101];
bool comp(DATA a, DATA b)
{
if(b.totalsolved > a.totalsolved)
{
return false;
}
else if(a.totalsolved == b.totalsolved)
{
if(a.total < b.total)
{
return true;
}
else
{
return a.id < b.id;
}
}
else
{
return true;
}
}
int main()
{
bool blank = false;
FOR(i, 1, 101)
{
teamdata[i].id = i;
}
int kases;
getint(kases);
cin.ignore();
cin.ignore();
stringstream ss;
string str;
int teamid, probid, timesplit;
char verdict;
while(kases--)
{
if(blank) pf("\n");
blank = true;
mem(attendedteam, 0);
FOR(i, 1, 101)
{
teamdata[i].total = 0;
teamdata[i].totalsolved = 0;
FOR(j, 1, 10)
{
teamdata[i].tried[j] = 0;
teamdata[i].solved[j] = 0;
}
}
while(true)
{
getline(cin, str);
if(SZ(str) == 0) break;
ss.clear();
ss<<str;
ss>>teamid>>probid>>timesplit>>verdict;
attendedteam[teamid] = 1;
if(teamdata[teamid].solved[probid] == 0)
{
if(verdict == 'C' )
{
teamdata[teamid].totalsolved++;
teamdata[teamid].solved[probid] = 1;
teamdata[teamid].total += teamdata[teamid].tried[probid] + timesplit;
}
else if(verdict == 'I')
{
teamdata[teamid].tried[probid] += 20;
}
}
}
vector<DATA>v;
FOR(i, 1, 101)
{
if(attendedteam[i])
{
v.pb(teamdata[i]);
}
}
sort(all(v), comp);
int len = SZ(v);
loop(i, len)
{
pf("%d %d %lld\n", v[i].id, v[i].totalsolved, v[i].total);
}
}
return 0;
}
(Timus) 1029. Ministry
0
/*
user: php
time: 0.093 sec
link: http://acm.timus.ru/problem.aspx?space=1&num=1029
*/
#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 10000000000
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
struct DATA{
int r, c;
void set(int i, int j)
{
r = i;
c = j;
}
};
ll dp[101][501][2][2];
ll cost[101][501];
DATA path[101][501];
int rows, columns;
ll rec(int r, int c, bool leftused, bool rightused)
{
ll &ret = dp[r][c][leftused][rightused];
if(ret != -1) return ret;
if(r == rows-1) return ret = cost[r][c];
ret = rec(r+1, c, 0, 0);
if(leftused == 0 && rightused == 0)
path[r][c].set(r+1, c);
if(rightused == 0 && c+1 < columns )
{
if(rec(r, c+1, 1, 0) < ret)
{
ret = dp[r][c+1][1][0];
if(leftused == 0)
path[r][c].set(r, c+1);
}
}
if(leftused == 0 && 0 < c )
{
if(rec(r, c-1, 0, 1 ) < ret )
{
ret = dp[r][c-1][0][1];
if(rightused == 0)
path[r][c].set(r, c-1);
}
}
ret += cost[r][c];
return ret;
}
int main()
{
ll mincost;
mem(dp, -1);
mem(path, -1);
cin>>rows>>columns;
loop(i, rows)
{
loop(j, columns)
{
cin>>cost[i][j];
}
}
mincost = INF;
DATA start;
start.r = 0;
loop(i, columns)
{
if(rec(0, i, 0, 0) < mincost)
{
start.c = i;
mincost = dp[0][i][0][0];
}
}
while(start.r != rows-1)
{
cout<<start.c+1<<" ";
start.set(path[start.r][start.c].r, path[start.r][start.c].c);
}
cout<<start.c + 1<<endl;
return 0;
}
(UVa) 437 – The Tower of Babylon
0
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=378
*/
#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 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(a) (a>0?a:-a)
#define MAXX 187
using namespace std;
struct DATA{
int sides[3];
void get(int i, int j, int k)
{
sides[2] = i;
sides[1] = j;
sides[0] = k;
}
};
DATA box[MAXX];
int dp[MAXX];
int len;
bool comp(DATA a, DATA b)
{
return a.sides[0] < b.sides[0];
}
bool fcomp(DATA a, DATA b)
{
return a.sides[0] < b.sides[0] && a.sides[1] < b.sides[1];
}
int longest(int u)
{
int &ret = dp[u];
if(ret != -1) return ret;
ret = 0;
for(int v=u+1; v<len; v++)
{
if( fcomp(box[u], box[v]) )
{
ret = max(ret, longest(v) );
}
}
ret += box[u].sides[2];
return ret;
}
int main()
{
//read();
int number_of_boxes;
int ss[3];
int j;
int result;
int kaseno = 0;
while(true)
{
getint(number_of_boxes);
if(number_of_boxes == 0) break;
loop(i, number_of_boxes)
{
getint(ss[0]); getint(ss[1]); getint(ss[2]);
j = 6*i;
box[j].get(ss[0], ss[1], ss[2]);
box[j+1].get(ss[0], ss[2], ss[1]);
box[j+2].get(ss[1], ss[0], ss[2]);
box[j+3].get(ss[2], ss[0], ss[1]);
box[j+4].get(ss[1], ss[2], ss[0]);
box[j+5].get(ss[2], ss[1], ss[0]);
}
len = number_of_boxes * 6;
sort(box, box + len, comp );
mem(dp, -1);
result = -INF;
loop(i, len)
{
result = max(result, longest(i) );
}
printf("Case %d: maximum height = %d\n", ++kaseno, result);
}
return 0;
}
(UVa) 255 – Correct Move
0
/*
user: php
time: 0.052 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=191
*/
#include<iostream>
#include<cstdio>
using namespace std;
int mod(int i)
{
if(i<0) return -i;
return i;
}
struct position{
int x, y;
void set(int state)
{
x = state % 8;
y = state / 8;
}
};
int main()
{
position king, queen, next;
int p, q, r;
while(scanf("%d %d %d", &p, &q, &r) == 3)
{
if(p == q)
{
printf("Illegal state\n");
}
else
{
if(q == r)
{
printf("Illegal move\n");
continue;
}
king.set(p);
queen.set(q);
next.set(r);
if(queen.x == next.x )
{
if( (king.x == next.x) && ( ( next.y <= king.y && king.y < queen.y) || (queen.y < king.y && king.y <= next.y) ) )
{
printf("Illegal move\n");
continue;
}
}
else if(queen.y == next.y)
{
if( (king.y == next.y) && ( ( next.x <= king.x && king.x < queen.x) || (queen.x < king.x && king.x <= next.x) ) )
{
printf("Illegal move\n");
continue;
}
}
else
{
printf("Illegal move\n");
continue;
}
if(mod(king.x - next.x) + mod(king.y - next.y) == 1)
{
printf("Move not allowed\n");
}
else
{
if(mod(king.x - next.x)== 1 && mod(king.y - next.y) == 1 && ((king.x == 0 &&(king.y = 0 || king.y == 7)) || (king.x == 7 &&(king.y == 0 || king.y == 7))) )
{
printf("Stop\n");
}
else
{
printf("Continue\n");
}
}
}
}
return 0;
}
(UVa) 11331 – The Joys of Farming
0
/*
user: php
time: 0.084 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2306
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<map>
#define loop(i, n) for(int i=0; i<n; i++)
#define pb push_back
#define ms(array, value) memset(array, value, sizeof(array))
#define MAXX 2002
#define getint(a) scanf("%d", &a)
#define SZ size()
using namespace std;
struct PAIR{
int first, second;
void mp(int i, int j)
{
first = i;
second = j;
}
};
PAIR point;
vector<int> Graph[MAXX];
vector<int> v[2];
vector<PAIR> pointlist;
bool visited[MAXX];
bool bfs(int node)
{
if(Graph[node].SZ == 0)
{
point.mp(1, 0);
pointlist.pb(point);
return false;
}
bool visitedByBC[2][MAXX];
loop(i, 2)
{
loop(j, MAXX)
{
visitedByBC[i][j] = false;
}
}
loop(i, MAXX) visited[i] = false;
v[0].clear();
v[1].clear();
bool cIndex = 0;
int p, q;
int *target;
point.mp(1, 0);
target = &point.second;
v[cIndex].pb(node);
visited[node] = true;
visitedByBC[cIndex][node] = true;
while(v[cIndex].SZ)
{
int len = v[cIndex].SZ;
int len2;
loop(i, len)
{
p = v[cIndex][i];
len2 = Graph[p].SZ;
loop(j, len2)
{
q = Graph[p][j];
if( ! visited[q] )
{
visited[q] = true;
visitedByBC[!cIndex][q] = true;
(*target)++;
v[!cIndex].pb(q);
}
else
{
if(visitedByBC[cIndex][q])
{
return true;
break;
}
}
}
}
v[cIndex].clear();
if(cIndex == 0)
{
cIndex = 1;
target = &point.first;
}
else
{
cIndex = 0;
target = &point.second;
}
}
pointlist.pb(point);
return false;
}
bool dp[MAXX][MAXX];
bool coloring(int p, int target)
{
if(target == 0 && p == pointlist.size())
{
return true;
}
if(target < 0) return false;
if(p == pointlist.size()) return false;
if(dp[p][target] == false) return false;
return dp[p][target] = coloring(p+1, target-pointlist[p].first) || coloring(p+1, target - pointlist[p].second);
}
using namespace std;
int main()
{
bool done;
int kases, u, v;
int b, c, a;
cin>>kases;
while(kases--)
{
done = false;
loop(i, MAXX)
{
Graph[i].clear();
visited[i] = false;
loop(j, MAXX)
{
dp[i][j] = true;
}
}
pointlist.clear();
getint(b);
getint(c);
getint(a);
loop(i, a)
{
getint(u);
getint(v);
Graph[u].pb(v);
Graph[v].pb(u);
}
int len = b + c + 1;
for(int i=1; i<len; i++)
{
if(!visited[i])
if(bfs(i))
{
printf("no\n");
done = true;
break;
}
}
if(done) continue;
if(coloring(0, b))
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
UnLucky Codes 