B. The Social Network
#include <bits/stdc++.h>
using namespace std;
#define mx 100005
typedef vector <int> VI;
int n, q;
int par[mx];
VI tmp[mx];
bitset <mx> mark;
int fnd(int u) {
if (par[u] == u) return u;
return par[u] = fnd(par[u]);
}
int main() {
// freopen("../templates/in", "r", stdin);
int tc; scanf("%d", &tc);
int t = 0;
while (tc--) {
mark = 0;
scanf("%d %d",&n, &q);
for (int i = 1; i <= n; i++) {
par[i] = i;
tmp[i].clear();
}
printf("Case %d:\n", ++t);
while (q--) {
int c; scanf("%d", &c);
if (c == 0) {
int u, v; scanf("%d %d", &u, &v);
int pu = fnd(u);
int pv = fnd(v);
if (pu == pv) continue;
if (tmp[pu].size() > tmp[pv].size()) {
swap(pu, pv);
}
for (auto x : tmp[pu]) tmp[pv].push_back(x);
par[pu] = pv;
mark[pv] = 1;
} else if (c == 1) {
int u, T;
scanf("%d %d", &u, &T);
int pu = fnd(u);
tmp[pu].push_back(T);
mark[pu] = 1;
} else {
int u, l, r;
scanf("%d %d %d", &u, &l, &r);
int pu = fnd(u);
int ans = 0;
if (mark[pu]) {
sort(tmp[pu].begin(), tmp[pu].end());
mark[pu] = 0;
}
auto lt = lower_bound(tmp[pu].begin(), tmp[pu].end(), l);
auto rt = upper_bound(tmp[pu].begin(), tmp[pu].end(), r);
if (rt > lt) ans = rt - lt;
printf("%d\n", ans);
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
#define mx 100005
typedef vector <int> VI;
int n, q;
int par[mx];
VI tmp[mx];
bitset <mx> mark;
int fnd(int u) {
if (par[u] == u) return u;
return par[u] = fnd(par[u]);
}
int main() {
// freopen("../templates/in", "r", stdin);
int tc; scanf("%d", &tc);
int t = 0;
while (tc--) {
mark = 0;
scanf("%d %d",&n, &q);
for (int i = 1; i <= n; i++) {
par[i] = i;
tmp[i].clear();
}
printf("Case %d:\n", ++t);
while (q--) {
int c; scanf("%d", &c);
if (c == 0) {
int u, v; scanf("%d %d", &u, &v);
int pu = fnd(u);
int pv = fnd(v);
if (pu == pv) continue;
if (tmp[pu].size() > tmp[pv].size()) {
swap(pu, pv);
}
for (auto x : tmp[pu]) tmp[pv].push_back(x);
par[pu] = pv;
mark[pv] = 1;
} else if (c == 1) {
int u, T;
scanf("%d %d", &u, &T);
int pu = fnd(u);
tmp[pu].push_back(T);
mark[pu] = 1;
} else {
int u, l, r;
scanf("%d %d %d", &u, &l, &r);
int pu = fnd(u);
int ans = 0;
if (mark[pu]) {
sort(tmp[pu].begin(), tmp[pu].end());
mark[pu] = 0;
}
auto lt = lower_bound(tmp[pu].begin(), tmp[pu].end(), l);
auto rt = upper_bound(tmp[pu].begin(), tmp[pu].end(), r);
if (rt > lt) ans = rt - lt;
printf("%d\n", ans);
}
}
}
}
C. ICGeSi Standings
#include<bits/stdc++.h>
using namespace std;
main()
{
int ts,cs=1;
scanf("%d",&ts);
while(ts--)
{
int n,ns[75]= {0},tp[75]= {0},frozen[75][75]= {0},flag=0,i,j,fro_solve[75]= {0};
scanf("%d",&n);
int a,b,c,m;
for(i=1; i<=n; i++)
{
scanf("%d%d%d",&a,&b,&c);
ns[a]=b;
tp[a]=c;
scanf("%d",&m);
fro_solve[a]=m;
for(j=1; j<=m; j++)
{
scanf("%d", &frozen[a][j]);
}
}
int rnk;
for(i=1; i<=n; i++)
{
cin>>rnk;
int n_s, t_p;
if(i==1)
{
ns[rnk]+=fro_solve[rnk];
for(j=1; j<=fro_solve[rnk]; j++)
{
tp[rnk]+=frozen[rnk][j];
}
n_s=ns[rnk];
t_p=tp[rnk];
}
else
{
if(n_s>=ns[rnk])
{
if(n_s==ns[rnk]&&t_p>tp[rnk])
{
flag=1;
}
}
else
{
flag=1;
}
for(j=1; j<=fro_solve[rnk]; j++)
{
if(n_s>=ns[rnk])
{
if(n_s==ns[rnk]&&t_p>tp[rnk])
{
flag=1;
break;
}
else
{
if(n_s-1>ns[rnk])
{
tp[rnk]+=frozen[rnk][j];
ns[rnk]+=1;
}
else if((n_s>ns[rnk])&&(t_p<=(tp[rnk]+frozen[rnk][j])))
{
tp[rnk]+=frozen[rnk][j];
ns[rnk]+=1;
}
else
{
break;
}
}
}
else
{
flag=1;
break;
}
}
n_s=ns[rnk];
t_p=tp[rnk];
}
}
if(flag==0)
{
printf("Case %d: We respect our judges :)\n",cs++);
}
else
{
printf("Case %d: Say no to rumour >:\n",cs++);
}
}
}
B. The Social Network
#include<bits/stdc++.h>
using namespace std;
#define max 10000007
int phi[max],sz=10000001;
long long com[max];
void phi_calc()
{
int i,j,cnt=0;
for(i=2; i<max; i++)
{
if(phi[i]==0)
{
phi[i]=i-1;
for(j=i*2; j<max; j=j+i)
{
cnt++;
if(phi[j]==0)
{
phi[j]=j;
}
phi[j]=phi[j]-(phi[j]/i);
}
}
}
unsigned long long s,d=0;
com[1]=1;
for(s=2; s<max; s++)
{
com[s]=com[s-1]+(long long)phi[s];
}
}
main()
{
phi_calc();
int ts,cs=1;
scanf("%d",&ts);
while(ts--)
{
long long n;
long long p;
scanf("%lld%lld",&n,&p);
long long ind=lower_bound(com,com+sz,p)-com;
long long ans=n/ind;
if(ans==0)
ans=-1;
printf("Case %d: %lld\n",cs++,ans);
}
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন