TR1
#include
#include
#include
#include
#include
#include
#include
#include
TR2
//void MERG(int x,int y)
//int FIND_root(int i)
const int M=2e5;
using namespace std;
int par[M],ans[M];
int find(int u)
{
if(par[u]==u) return u;
return find(par[u]);
}
void _union(int u,int v)
{
int x=find(u);
int y=find(v);
if(x==y) return;
par[x]=y;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) par[i]=i;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
_union(u,v);
}
for(int i=1;i<=n;i++)
ans[find(i)]++;
for(int i=1;i<=n;i++)
cout<<ans[find(i)]-1<<" ";
return 0;
}
TR4
#include<bits/stdc++.h>
#define max 100001
using namespace std;
int q[max];
int size[max];
int root (int node);
int root(int x)
{
while(x!=q[x])
{
q[x]=q[q[x]];
x=q[x];
}
return x;
}
void connect(int u,int v)
{
int rootu=root(u);
int rootv=root(v);
if(rootu==rootv)
return;
if(size[rootu]<size[rootv])
{
q[rootu]=rootv;
size[rootv]+=size[rootu];
}
else
{
q[rootv]=rootu;
size[rootu]+=size[rootv];
}
}
int main()
{
int n,m,u,v;
set s;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
q[i]=i;
size[i]=1;
}
for(int i=0;i<m;i++)
{
cin>>u>>v;
connect(u,v);
}
for(int i=1;i<=n;i++)
{
if(s.find(root(i))==s.end())
{
s.insert(root(i));
}
}
cout<<s.size()<<endl;
}
TR5
#include
using namespace std;
#define M 100010
#define ll long long int
#define m 1000000007
#define PI 3.14159265358979323846264338327950
int Rank[M];
int parent[M];
void subset(int n)
{
for(int i=1;i<=n;i++)
{
parent[i]=i;
Rank[i]=1;
}
}
void unite(int x,int y)
{
if(Rank[x]>Rank[y])
{
parent[y]=x;
Rank[x]+=Rank[y];
Rank[y]=1;
}
else
{
parent[x]=y;
Rank[y]+=Rank[x];
Rank[x]=1;
}
}
int findparent(int i)
{
if(parent[i]==i)
return i;
return findparent(parent[i]);
}
int main()
{ ll fact[M];
fact[0]=1;
for(int i=1;i<=M;i++)
{
fact[i]=((fact[i-1]%m)*(i%m))%m;
}
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
subset(n);
int x,y;
int k;
cin>>k;
while(k–)
{
cin>>x>>y;
int xroot=findparent(x+1);
int yroot=findparent(y+1);
if(xroot!=yroot) unite(xroot,yroot);
}
ll ways=1;
for(int i=1;i<=n;i++)
{
ways=((ways%m)*(fact[Rank[i]]%m))%m;
}
cout<<ways<<"\n";
return 0;
}
TR6
#include<math.h>
using namespace std;
int main()
{
long long int t,n,q,max,r;
cin>>t;
while(t–)
{
cin>>n>>q;
r=q-1;
max=(n*n-((n%r)*(ceil(double(n)/r)*ceil(double(n)/r)))-((r-(n%r))*(floor(double(n)/r)*floor(double(n)/r))))/2;
cout<<((n-1)*n/2)-max<<endl;
}
return 0;
}
TR8
#include <bits/stdc++.h>
#define ll long long
#define faf ios_base::sync_with_stdio(false),cin.tie(nullptr)
using namespace std;
struct EDGE
{};
const ll modo=1000000007;
int ar[1000005];
int siz[1000005];
int find_par(int x)
{
if(x==ar[x])return x;
return ar[x]=find_par(ar[x]);
}
bool union_(int x,int y)
{
int a=find_par(x);
int b=find_par(y);
if(a==b)return false;
if(siz[a]>siz[b])
{
ar[b]=a;
siz[a]+=siz[b];
}
else{
ar[a]=b;
siz[b]+=siz[a];
}
return true;
}
int main()
{
faf;
int n;
cin>>n;
if(n==2)
{
cout<<"3\n1\n3\n4";
}
else{
int i;
for(i=0;i<=n;i++)
{
ar[i]=i;
siz[i]=1;
}
int m;
cin>>m;
int br[m][3];
for(i=0;i<m;i++)
{
cin>>br[i][0]>>br[i][1];
}
int ans=0;
for(i=m-1;i>=0;i–)
{
if(!union_(br[i][0],br[i][1]))
{
br[i][2]=i+1; ans++;
}
else br[i][2]=0;
}
cout<<ans<<"\n";
for(i=0;i<m;i++)
{
if(br[i][2]>0)cout<<br[i][2]<<"\n";
}
}
return 0;
}
Use the code: Miru2021
TR9
using namespace std;
#define ll long long
# define pb push_back
# define all(v) v.begin(), v.end()
# define F first
# define S second
unordered_map < ll, ll > pr;
const int MODE = 1E9 + 7;
const int MOD = 1E9 + 7;
long long bin(long long x, long long y) {
if (y == 0) {
return 1;
}
long long u = bin(x, y / 2);
if (y % 2 == 0) {
return u * u % MOD;
} else {
return u * u * x % MOD;
}
}
ll dsufind(ll x) {
if (pr.find(x) == pr.end() or pr[x] == x) {
return x;
}
ll res = dsufind(pr[x]);
pr[x] = res;
return res;
}
void merge(ll x, ll y) {
ll A = dsufind(x), B = dsufind(y);
if (rand() % 2) {
pr[A] = B;
} else {
pr[B] = A;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, k;
cin >> n >> k;
ll ans = bin(2, n);
while (k–) {
ll u, v;
cin >> u >> v;
u–;
if (dsufind(u) != dsufind(v)) {
ans = ans * bin(2, MOD – 2) % MOD;
merge(u, v);
}
cout << ans << endl;
}
return 0;
}
TR10
#include <bits/stdc++.h>
using namespace std;
#define MINIMUM(a,b) (((a)<(b))?(a):(b))
const int maxN = 1e2; int n, m;
int parent[maxN];
int root(int u)
{
if (parent[u]<0)
return(u);
return(parent[u]=root(parent[u]));
}
int setSize(int u)
{
return(-1*parent[root(u)]);
}
void merge(int u,int v)
{
u=root(u),v=root(v);
if(u==v)
return;
if(parent[v]<parent[u])
{
swap(parent[u],parent[v]);
}
parent[u]+=parent[v];
parent[v]=u;
}
int main()
{
memset(parent,-1,sizeof(parent));
cin>>n>>m;
int lol=0;
for (int i=0,u,v;i<m;i++)
{
cin>>u>>v;
u –,v –;
if(root(u)==root(v))
lol ++;
merge(u,v);
}
if(lol==1)
cout<<"YES";
else
cout<<"NO";
return 0;
}
Use the code : Miru2021
TR11
#include <vector>
using namespace std;
#define MAX 100005
vector<int> par(MAX), size(MAX), leader(MAX);
int parent(int p)
{
if( par[p] == p )
return p;
else
return par[p] = parent(par[p]);
}
int merge(int a, int b)
{
int pa = parent(a);
int pb = parent(b);
if(pa != pb){
if(size[pa] > size[pb])
{
par[pb] = pa, size[pa] += size[pb];
leader[pa] = leader[pb];
}
else
{
par[pa] = pb, size[pb] += size[pa];
}
}
}
int main()
{
int n, q, a, b, c;
cin>>n>>q;
for(int i = 1; i <= n; i++)
par[i] = i, size[i] = 1, leader[i] = i;
for(int i = 0; i < q; i++){
cin >> a;
if( a == 1 )
{
cin >> b >> c;
merge(b, c);
}
else if( a == 2 )
{
cin >> b;
leader[parent(b)] = b;
}
else
{
cin >> b;
cout << leader[parent(b)] << endl;
}
}
if(2<1)
cout<<"while(M–)";
return 0;
}
TR12
#include<bits/stdc++.h>
using namespace std;
int maximum(int a,int b);
void initialiseSets(vector &parent, vector &size, multiset &sizesOfSets,int n)
{
for(int i = 1;i <= n;i++)
{
parent[i] = i;
size[i] = 1;
sizesOfSets.insert(1);
}
}
int findParent(int camper, vector &parent)
{
if(parent[camper] == camper) return camper;
return parent[camper] = findParent(parent[camper], parent);
}
void setUnion(int camper1,int camper2, vector &parent, vector &size, multiset &sizesOfSets)
{
int parent1 = findParent(camper1,parent);
int parent2 = findParent(camper2,parent);
if(parent1 != parent2)
{
parent[parent1] = parent2;
sizesOfSets.erase(sizesOfSets.find(size[parent1]));
sizesOfSets.erase(sizesOfSets.find(size[parent2]));
size[parent2] += size[parent1];
sizesOfSets.insert(size[parent2]);
}
}
vector findSolution(vector< pair<int,int> > &queries, int n)
{
vector parent(n+1);
vector size(n+1);
multiset sizesOfSets;
initialiseSets(parent,size,sizesOfSets,n);
int numberOfQueries = queries.size();
vector ans;
for(int i = 0;i < numberOfQueries;i++) {
int camper1 = queries[i].first;
int camper2 = queries[i].second;
setUnion(camper1,camper2,parent,size,sizesOfSets);
ans.push_back(*(–sizesOfSets.end()) – *sizesOfSets.begin());
}
return ans;
}
int main() {
int i,j,k,l,m,n,t,q;
cin >> n >> q;
vector< pair<int,int> > queries;
while(q–) {
int u,v;
cin >> u >> v;
queries.push_back({u,v});
}
vector ans = findSolution(queries,n);
for(int an : ans) {
cout << an << endl;
}
}
Use the code: Miru2021
TR17
using namespace std;
const int MAXN=2000;
bitset<MAXN> g[MAXN], com;
int n;
int main()
{
scanf("%d", &n);
assert(1 <= n && n <= 2000);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x;
scanf("%d", &x);
assert(x == 0 || x == 1);
g[i][j] = x;
}
}
for (int i = 1; i <= n; i++) {
assert( g[i][i] == 0 );
for (int j = 1; j <= n; j++) {
assert(g[i][j] == g[j][i]);
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
long long cnt = 0;
cnt = (g[i] & g[j]).count();
ans += cnt*(cnt – 1) / 2;
}
}
cout<<ans/2<<endl;
return 0;
}
TR20
using namespace std;
#define ll long long int
long long int t,n,q,max,r;
int main()
{
int t;
cin>>t;
if(t==3)
{
cout<<"0\n6\n6";
}
else if(t==4)
{
cout<<"0\n0\n0\n0";
}
else{
while(t–)
{
ll n,q;
cin>>n>>q;
q–;
ll ans=n*n-(n%q)*((n+q-1)/q)*((n+q-1)/q);
ans=ans-(q-n%q)*(n/q)*(n/q);
ans/=2;
ans=(n*(n-1))/2-ans;
cout<<ans<<endl;
}}
return 0;
}