Regroup
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1057 Accepted Submission(s):
297
build software to help them regroup the battalions or companies.
As the
tradition of army, soldiers are rated according his or her abilities, taking the
rate as an integer. The fighting capacity of a company is determined by the
soldier in this company whose rate is lowest. Now the recruits those rated are
coming and join to their companies according to the order form HQ.
With the
coming of new recruits, a big regroup action reached, asking to merge some
companies into one. The designation of a company, however, will not be canceled,
but remain for memorialize what the company is done, means the designation of
the company is still exist, but the company is gone, so it is unable to ask
recruits to join this company, or merge the company into others.
A strange
thing is, the orders sometimes get wrong, send newbie to a company which is
already merged into another, or mentioned some only-designation-existed
companies. Such order could be rejected.
The brigadier wants to know every
change of each order, so the program should able to report the status of every
order, telling whether it is accept, and can query the fighting capacity of
specified company. (To simplify, companies are numbered from 0 to n-1
For each case, the
integers in first line, n, k, m, telling that there are n companies, k soldiers
already, and m orders needs be executed. (1<=n ,k ,m<=100000).
Then k
lines with two integers R and C for each, telling a soldier with rate R is now
in company C
Then m lines followed, containing 3 kinds of orders, in upper
case:
AP x y
A recruit with ability rate x were asked to join company y.
(0<=x<2^31, 0<=y<n)
MG x y
Company x and company y is
merged. The new company is numbered as x. (0<=x, y<n)
GT
x
Report the fighting capacity of company x. (0<=x<n)
result.
For AP and MG order, print “Accept” if it is able to be done, and
execute it, or “Reject” if it is an illegal order.
For GT order, if company x
is still exist (not merged into others), print as “Lowest rate: y.” which y is
the minimal rate of soldiers in this company. If there is no one in this
company, tell "Company x is empty." If company x is already merged into others,
print "Company x is a part of company z." z is the company where the company x
is in.
Print a blank line after each case
5 0
5 1
5 2
5 1
5 0
GT 0
GT 3
AP 3 3
GT 3
GT 4
MG 3 4
GT 4
MG 1 3
GT 4
GT 1
Company 3 is empty.
Accept
Lowest rate: 3.
Company 4 is empty.
Accept
Company 4 is a part of company 3.
Accept
Company 4 is a part of company 1.
Lowest rate: 3.
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int f[100005];
int d[100005];
int fig[100005];
int vis[100005];
int getf(int v){return f[v]==v?v:f[v]=getf(f[v]);}
int main()
{
int n,m,i,j,k,x,y,q,r,c;
char s[30];
while(cin>>n>>k>>q){
memset(d,0,sizeof(d));
memset(fig,inf,sizeof(fig));
for(i=0;i<n;++i) f[i]=i,vis[i]=1;
for(i=1;i<=k;++i){
scanf("%d%d",&r,&c);
fig[c]=min(fig[c],r);
d[c]++;
}
while(q--){
scanf(" %s",s);
if(!strcmp(s,"AP")){ scanf("%d%d",&x,&y);
if(!vis[y]) puts("Reject");
else {
puts("Accept");
d[y]++;
fig[y]=min(fig[y],x);
}
}
else if(!strcmp(s,"MG")){ scanf("%d%d",&x,&y);
if(!vis[x]||!vis[y]||(x==y)) {puts("Reject");continue;}
puts("Accept");
d[x]+=d[y];
d[y]=0;
vis[y]=0;
fig[x]=min(fig[x],fig[y]);
fig[y]=inf;
f[y]=x;
}
else if(!strcmp(s,"GT")){ scanf("%d",&y);
if(vis[y]&&d[y]>0) printf("Lowest rate: %d.\n",fig[y]);
else if(vis[y]&&d[y]==0) printf("Company %d is empty.\n",y);
else if(!vis[y]) printf("Company %d is a part of company %d.\n",y,getf(y));
}
} puts("");
}
return 0;
}