/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2234
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#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 dd double
#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
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 11002
vector<int>graph[MAXX];
vector< pair<int, pair<int, int> > >edges;
char color[MAXX];
int cntNodes, cntEdges;
bool possible;
int parent[MAXX];
void bfs()
{
color[1] = 0;
queue<int>Q;
Q.push(1);
int u, v;
while( !Q.empty() )
{
u = Q.front(); Q.pop();
loop(i, SZ(graph[u]))
{
v = graph[u][i];
if(color[v] == color[u])
{
possible = false;
return;
}
if(color[v] == -1)
{
color[v] = color[u]?0:1;
Q.push(v);
}
}
}
}
int find(int u)
{
if(parent[u] == u)
{
return u;
}
else return parent[u] = find(parent[u]);
}
int main()
{
int p, q, w;
while(1)
{
getint(cntNodes);
if(!cntNodes) break;
for(int i=1; i<=cntNodes; i++)
{
graph[i].clear();
}
edges.clear();
getint(cntEdges);
loop(i, cntEdges)
{
getint(p); getint(q); getint(w);
graph[p].pb(q);
graph[q].pb(p);
edges.pb( mp(w, mp(p, q)));
}
mem(color, -1);
possible = 1;
bfs();
if(!possible)
{
pf("Invalid data, Idiot!\n");
}
else
{
for(int i=1; i<=cntNodes; i++) parent[i] = i;
ll minCost = 0;
sort(all(edges));
loop(i, SZ(edges))
{
p = find(edges[i].sc.fr);
q = find(edges[i].sc.sc);
w = edges[i].fr;
if(p != q || w < 0)
{
minCost += w;
parent[p] = q;
}
}
pf("%lld\n", minCost);
}
}
return 0;
}
Monthly Archives: March 2013
(UVa) 10034 Freckles
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=975
*/
#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
#define pdd pair<double, double>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
#define MAXX 102
int cntPoints;
pdd points[MAXX];
int parent[MAXX];
template<typename T>
T sqr(T a)
{
return a*a;
}
int find(int u)
{
if(parent[u] == u)
{
return u;
}
return parent[u] = find(parent[u]);
}
int main()
{
int kases;
getint(kases);
double p, q;
double minCost;
bool blank = false;
while(kases--)
{
getint(cntPoints);
loop(i, cntPoints)
{
sf("%lf %lf", &p, &q);
points[i] = mp(p, q);
}
vector<pair<double, pair<int, int> > > dists;
loop(i, cntPoints)
{
FOR(j, i+1, cntPoints)
{
dists.pb( mp( sqrt( sqr(points[i].fr - points[j].fr) + sqr(points[i].sc - points[j].sc) ) , mp(i, j) ) );
}
}
sort(all(dists));
loop(i, cntPoints)
{
parent[i] = i;
}
minCost = 0;
int u, v;
loop(i, SZ(dists))
{
u = find(dists[i].sc.fr);
v = find(dists[i].sc.sc);
if(u != v)
{
parent[u] = v;
minCost += dists[i].fr;
}
}
if(blank) pf("\n");
else blank = true;
pf("%.2lf\n", minCost);
}
return 0;
}
(UVa) 514 Rails
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=455
*/
#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 1002
int cntCells;
int main()
{
int id;
while(getint(cntCells) && cntCells!= 0)
{
while(getint(id) && id != 0)
{
if(!id) break;
queue<int>B;
B.push(id);
FOR(i, 1, cntCells)
{
getint(id);
B.push(id);
}
int pos = 1;
stack<int>station;
while( !B.empty() )
{
while(station.empty() || station.top() !=B.front() )
{
if(pos > cntCells) break;
station.push(pos);
pos++;
}
if(station.top() == B.front() )
{
station.pop();
B.pop();
}
else
{
break;
}
}
if(B.empty())
{
pf("Yes\n");
}
else
{
pf("No\n");
}
}
pf("\n");
}
return 0;
}
(UVa) 146 – ID Codes
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=82
*/
#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 main()
{
string ss;
while(true)
{
cin>>ss;
if(ss == "#") break;
if( !next_permutation(all(ss)))
{
pf("No Successor\n");
}
else
{
cout<<ss<<endl;
}
}
return 0;
}
(UVa) 558 – Wormholes
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=499
*/
#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 2002
struct DATA{
int p, q, w;
};
int stars, countPaths;
DATA paths[MAXX];
ll dist[MAXX];
bool bellmanFord()
{
loop(i, stars)
{
dist[i] = INF;
}
dist[1] = 0;
loop(i, stars-1)
{
loop(j, countPaths)
{
if( dist[ paths[j].p ] + paths[j].w < dist[ paths[j].q ] )
{
dist[ paths[j].q ] = dist[ paths[j].p ] + paths[j].w;
}
}
}
loop(j, countPaths)
{
if( dist[ paths[j].p ] + paths[j].w < dist[ paths[j].q ] )
{
return false;
}
}
return true;
}
int main()
{
int kases;
getint(kases);
int p, q, w;
while(kases--)
{
getint(stars); getint(countPaths);
loop(i, countPaths)
{
getint(paths[i].p); getint(paths[i].q); getint(paths[i].w);
}
if(!bellmanFord())
{
pf("possible\n");
}
else
{
pf("not possible\n");
}
}
return 0;
}
(timus) 1078. Segments
0
/*
link: http://acm.timus.ru/problem.aspx?space=1&num=1078
*/
#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
#define MAXX 22
#define MAXX 10002
using namespace std;
struct DATA{
int id, left, right;
};
bool comp(DATA a, DATA b)
{
if(a.left < b.left)
{
return true;
}
else if(a.left == b.left)
{
return a.right < b.right;
}
else
{
return false;
}
}
int cnt;
DATA ara[MAXX];
int LisLen = 0;
int L[MAXX];
void NlogK()
{
int temp = cnt+1;
int I[temp];
I[0] = INF;
FOR(i, 1, temp)
{
I[i] = -INF;
}
int left, u, right, mid;
loop(i, cnt)
{
u = ara[i].right;
left = 0;
right = LisLen;
while( left <= right )
{
mid = (left + right)/2;
if(I[mid] > u)
{
left = mid+1;
}
else
{
right = mid - 1;
}
}
I[left] = u;
L[i] = left;
LisLen = max(LisLen, left);
}
}
int main()
{
getint(cnt);
loop(i, cnt)
{
ara[i].id = i;
getint(ara[i].left); getint(ara[i].right);
}
sort(ara, ara+cnt, comp);
NlogK();
cout<<LisLen<<endl;
int last_taken = -INF;
for(int i=cnt-1; i>-1; i--)
{
if(L[i] == LisLen && ara[i].right > last_taken)
{
pf("%d", ara[i].id + 1);
LisLen--;
if(LisLen) pf(" ");
}
}
pf("\n");
}
(timus) 1073. Square Country
0
/*
link: http://acm.timus.ru/problem.aspx?space=1&num=1073
*/
#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 1000000
#define mod abs
#define pf printf
#define sf scanf
#define MAXX 60002
using namespace std;
int dp[MAXX];
int rec(int remain)
{
int &ret = dp[remain];
if(ret != -1) return ret;
int root = sqrt(remain);
ret = INF;
for(int i=1; i<=root; i++)
{
ret = min(ret, rec(remain - i*i));
}
return ++ret;
}
using namespace std;
int main()
{
int target;
getint(target);
mem(dp, -1);
dp[0] = 0;
cout<<rec(target)<<endl;
}
(UVa) 208 – Firetruck
0
/*
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=144
*/
#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 abs
#define pf printf
#define sf scanf
#define MAXX 22
using namespace std;
int target;
vector<int>graph[MAXX];
int result[MAXX];
bool done[MAXX];
int cnt;
void rec(int pos)
{
if(result[pos] == target)
{
cnt++;
pf("1");
pos++;
FOR(i, 1, pos)
{
pf(" %d", result[i]);
}
pf("\n");
return;
}
int u = result[pos];
int len = SZ(graph[u]);
pos++;
int v;
loop(i, len)
{
v = graph[u][i];
if(!done[v])
{
result[pos] = v;
done[v] = true;
rec(pos);
done[v] = false;
}
}
}
bool bfs(int u)
{
bool visited[MAXX];
mem(visited, 0);
visited[1] = true;
queue<int>Q;
Q.push(u);
while( !Q.empty() )
{
int u = Q.front(); Q.pop();
int len = SZ(graph[u]);
loop(i, len)
{
int v = graph[u][i];
if(v == target)
{
return true;
}
if(!visited[v])
{
visited[v] = true;
Q.push(v);
}
}
}
return false;
}
int main()
{
int kaseno = 0;
int p, q;
while(getint(target) == 1)
{
loop(i, MAXX)
{
graph[i].clear();
}
while(true)
{
getint(p); getint(q);
if(p == 0 && q == 0) break;
graph[p].pb(q);
graph[q].pb(p);
}
pf("CASE %d:\n", ++kaseno);
if(bfs(1) == 0)
{
pf("There are 0 routes from the firestation to streetcorner %d.\n", target);
}
else
{
cnt = 0;
loop(i, MAXX)
{
sort(all(graph[i]));
}
mem(done, 0);
done[1] = true;
result[0] = 1;
rec(0);
pf("There are %d routes from the firestation to streetcorner %d.\n", cnt, target);
}
}
return 0;
}
(lightoj) 1164 – Horrible Queries
0
/*
link: http://lightoj.com/volume_showproblem.php?problem=1164
*/
#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 abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 100002
ll sum[4*MAXX];
int lazy[4*MAXX];
void updateNode(int idx, int st, int ed, int value)
{
sum[idx] += value * (ed - st + 1);
lazy[idx] += value;
}
void update(int idx, int st, int ed, int i, int j, int value)
{
if(st == i && ed == j)
{
sum[idx] += value * (ed - st + 1);
lazy[idx] += value;
return;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed)>>1;
if(lazy[idx] > 0)
{
updateNode(l, st, mid, lazy[idx]);
updateNode(r, mid+1, ed, lazy[idx]);
}
lazy[idx] = 0;
if(j<=mid)
{
update(l, st, mid, i, j, value);
}
else if(mid < i)
{
update(r, mid+1, ed, i, j, value );
}
else
{
update(l, st, mid, i, mid, value);
update(r, mid+1, ed, mid+1, j, value);
}
sum[idx] = sum[l] + sum[r];
}
ll query(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)>>1;
if(lazy[idx] > 0)
{
updateNode(l, st, mid, lazy[idx]);
updateNode(r, mid+1, ed, lazy[idx]);
}
lazy[idx] = 0;
if(j<=mid)
{
return query(l, st, mid, i, j);
}
else if(mid < i)
{
return query(r, mid+1, ed, i, j);
}
else
{
return query(l, st, mid, i, mid) + query(r, mid+1, ed, mid+1, j);
}
}
int main()
{
//read();
//write();
int kases, kaseno = 0;
getint(kases);
int cmd, x, y, v;
int elements, cnt_query;
while(kases--)
{
pf("Case %d:\n", ++kaseno);
getint(elements);
getint(cnt_query);
mem(sum, 0);
mem(lazy, 0);
loop(t, cnt_query)
{
sf("%d%d%d", &cmd, &x, &y);
x++;
y++;
if(cmd == 0)
{
getint(v);
update(1, 1, elements, x, y, v);
}
else
{
pf("%lld\n", query(1, 1, elements, x, y));
}
}
}
}
(lightoj) 1087 – Diablo
0
/*
link: http://lightoj.com/volume_showproblem.php?problem=1087
*/
#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 abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 150005
int cnt_elements[4*MAXX];
vector<int>ids;
int cnt;
int cnt_query;
int total;
void update(int idx, int st, int ed, int pos, int value)
{
//cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<endl;
if(st == pos && pos == ed)
{
cnt_elements[idx] += value;
return;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed) / 2;
if(pos <= mid)
{
update(l, st, mid, pos, value);
}
else
{
update(r, mid+1, ed, pos, value);
}
cnt_elements[idx] = cnt_elements[l] + cnt_elements[r];
}
int get(int idx, int st, int ed, int pos)
{
//cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<" and number of elements = "<<cnt_elements[idx]<<endl;
cnt_elements[idx]--;
if(st == ed )
{
return st;
}
int l = idx<<1;
int r = l + 1;
int mid = (st + ed) / 2;
if( pos <= cnt_elements[l] )
{
return get(l, st, mid, pos);
}
else
{
return get(r, mid +1, ed, pos - cnt_elements[l]);
}
}
int main()
{
//read();
//write();
int kases, kaseno = 0;
getint(kases);
int num;
char cmd[4];
int id;
int temp;
while(kases--)
{
pf("Case %d:\n", ++kaseno);
getint(cnt); getint(cnt_query);
total = cnt + cnt_query;
temp = cnt;
mem(cnt_elements, 0);
ids.clear();
loop(i, cnt)
{
getint(num);
ids.pb(num);
update(1, 1, total, i+1, 1);
}
loop(t, cnt_query)
{
sf("%s", cmd);
getint(num);
if(cmd[0] == 'c')
{
if(num > cnt)
{
pf("none\n");
continue;
}
cnt--;
id = get(1,1, total, num);
pf("%d\n", ids[id-1]);
}
else
{
ids.pb(num);
temp++;
cnt++;
update(1, 1, total, temp, 1);
}
}
}
return 0;
}
UnLucky Codes 